Largest rectangle in a histogram (bar chart)
Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.
public int largestRectangleArea(int[] heights) {
int len = heights.length;
Stack<Integer> s = new Stack<>();
int maxArea = 0;
for (int i = 0; i <= len; i++){
int h = (i == len ? 0 : heights[i]);
if (s.isEmpty() || h >= heights[s.peek()]) {
s.push(i);
} else {
int tp = s.pop();
maxArea = Math.max(maxArea, heights[tp] * (s.isEmpty() ? i : i - 1 - s.peek()));
i--;
}
}
return maxArea;
}Related Problems
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring.
You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
Return the max sliding window, ie an array with the max of the k numbers within the window, for each position as the window moves across the input. ex: [6,2,1,4] with k=2 would return [6,2,4]