//Given an array of integers heights representing the histogram's bar height whe
//re the width of each bar is 1, return the area of the largest rectangle in the h
//istogram.
//
//
// Example 1:
//
//
//Input: heights = [2,1,5,6,2,3]
//Output: 10
//Explanation: The above is a histogram where width of each bar is 1.
//The largest rectangle is shown in the red area, which has an area = 10 units.
//
//
// Example 2:
//
//
//Input: heights = [2,4]
//Output: 4
//
//
//
// Constraints:
//
//
// 1 <= heights.length <= 105
// 0 <= heights[i] <= 104
//
// Related Topics Array Stack Monotonic Stack
// 👍 11428 👎 160
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public int largestRectangleArea(int[] receive){
int maxArea = 0;
int[] left = new int[receive.length];
int[] right = new int[receive.length];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < receive.length; i++) {
while (!stack.isEmpty() && receive[stack.peek()] >= receive[i]) {
stack.pop();
}
if (stack.isEmpty()) {
left[i] = -1;
} else {
left[i] = stack.peek();
}
stack.push(i);
}
stack.clear();
for (int i = receive.length - 1; i >= 0; i--) {
while (!stack.isEmpty() && receive[stack.peek()] >= receive[i]) {
stack.pop();
}
if (stack.isEmpty()) {
right[i] = receive.length;
} else {
right[i] = stack.peek();
}
stack.push(i);
}
for (int i = 0; i < receive.length; i++) {
maxArea = Math.max(maxArea, (right[i] - left[i] - 1) * receive[i]);
}
return maxArea;
}
}
//leetcode submit region end(Prohibit modification and deletion)
