1762. Buildings With an Ocean View
Explanation:
To solve this problem, we need to find the buildings with an ocean view, which means the buildings have a greater height to their right. We can iterate through the buildings from right to left and keep track of the maximum height seen so far. If the current building's height is greater than the maximum height seen so far, it has an ocean view.
Algorithm:
- Initialize an empty stack to store the indices of buildings with an ocean view.
- Iterate over the buildings from right to left:
- If the stack is empty, push the current building index to the stack.
- If the current building height is greater than the height of the building at the top of the stack, pop elements from the stack until either the stack becomes empty or the top building has a greater height.
- Push the current building index to the stack.
- The stack now contains the indices of buildings with an ocean view.
Time Complexity: O(N) - where N is the number of buildings. Space Complexity: O(N) - for the stack to store the indices.
: :
public int[] findBuildings(int[] heights) {
Stack<Integer> stack = new Stack<>();
for (int i = heights.length - 1; i >= 0; i--) {
if (stack.isEmpty() || heights[i] > heights[stack.peek()]) {
stack.push(i);
}
}
int[] result = new int[stack.size()];
for (int i = 0; i < result.length; i++) {
result[i] = stack.pop();
}
return result;
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.