There are n buildings in a line. You are given an integer array heights of size n that represents the heights of the buildings in the line.
The ocean is to the right of the buildings. A building has an ocean view if the building can see the ocean without obstructions. Formally, a building has an ocean view if all the buildings to its right have a smaller height.
Return a list of indices (0-indexed) of buildings that have an ocean view, sorted in increasing order.
Example 1:
Input: heights = [4,2,3,1] Output: [0,2,3] Explanation: Building 1 (0-indexed) does not have an ocean view because building 2 is taller.
Example 2:
Input: heights = [4,3,2,1] Output: [0,1,2,3] Explanation: All the buildings have an ocean view.
Example 3:
Input: heights = [1,3,2,4] Output: [3] Explanation: Only building 3 has an ocean view.
Example 4:
Input: heights = [2,2,2,2] Output: [3] Explanation: Buildings cannot see the ocean if there are buildings of the same height to its right.
Constraints:
1 <= heights.length <= 10^51 <= heights[i] <= 10^9
The description was taken from https://leetcode.com/problems/buildings-with-an-ocean-view/.
#Check Current Max#O(N) Time, O(1) Space
class Solution:
def findBuildings(self, heights: List[int]) -> List[int]:
output = []
max_height = -1
for i in range(len(heights)-1, -1, -1):
if heights[i] > max_height:
output.append(i)
max_height = heights[i]
return output[::-1]#Monotonic Stack#O(N) Time, O(1) Spaceclass Solution:
def findBuildings(self, heights: List[int]) -> List[int]:
output, stack = [], []
for i, height in enumerate(heights):
if stack and height < stack[-1][0]:
stack.append((height, i))
continue
while stack and height >= stack[-1][0]:
stack.pop()
stack.append((height, i))
for height in stack:
output.append(height[1])
return outputFor a building to have a view, it needs to be taller than each building to its right.
We can check this condition by traversing the heights of the buildings from right to left and seeing if each building is taller than the tallest building to its right.
If it is, that building has a view.
Let's start by initializing our output and maximum height variable.
output = []
max_height = -1
Now, we will traverse the heights from right to left.
If the building within the current iteration has a height greater than each height to its right, then this building has a view so we will append its index to the output and update the maximum height to this building.
for i in range(len(heights)-1, -1, -1):
if heights[i] > max_height:
output.append(i)
max_height = heights[i]
Once we have our output array of buildings, it will be reversed since we appended the buildings to it going from right to left.
We will just need to reverse it once more and return it.
return output[::-1]
Even though this algorithm may not be as intuitive as the first one, this algorithm may have popped into our heads.
A monotonic decreasing stack can be used to find each greater element for each number within an array. Traditionally, we would traverse the heights array and if we had a height less than the top value of a stack, we would just add the height onto the stack and continue. If we had a height greater than the top of the stack, we would pop off each smaller building than the current one and mark that the next greater height for those buildings is the current height.
After we found the next greater height for each building where it existed, each building that didn't have one would still be on the stack.
Those heights without a greater value still on the stack would be the buildings that have a view because no taller building obstructed it.
Let's start by initializing our output and stack.
output, stack = [], []
Now, we can begin traversing the heights array.
If the current height is less than the top value on the stack, then each building on the stack still has a view so we will append the current building's height and continue.
for i, height in enumerate(heights):
if stack and height < stack[-1][0]:
stack.append((height, i))
continue
Otherwise, the current building is obstructing the view of each shorter building on the stack.
Let's pop off all of those shorter buildings than the current one since we know now they have no view.
while stack and height >= stack[-1][0]:
stack.pop()
Once we have each shorter building popped off the stack, we will append the current one and its index.
stack.append((height, i))
Every building still on the stack has no taller building to the right of it, let's iterate through the stack and append their indices to the output.
for height in stack:
output.append(height[1])
Once we have the list of buildings with a view, let's return it.
return output