LeetCode 84. Largest Rectangle in Histogram (Monotonic Stack Template)

 84. Largest Rectangle in Histogram

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.

 

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

	class Solution {
	public:
	/*
	Monotonic Stack
	- common features
	1. Range Query problem
	2. Asking minima or maxima
	3. Popped value from stack, never used again
	- means must update answer
	*/
	int largestRectangleArea(vector<int>& heights) {
	// trick: calculating for end
	heights.push_back(0);
	// monotonic stack
	stack<int> ms;
	int ans = 0;
	int n = heights.size();
	for(int i = 0; i < n; i++){
	while(!ms.empty() and heights[ms.top()] > heights[i]){
	int height = heights[ms.top()];
	ms.pop();
	// edge case: if stack is empty
	int width = ms.empty() ? i : i - ms.top() - 1;
	// update answer
	ans = max(ans, height * width);
	}
	// stacking height's indexes, which is useful for calculcating width
	ms.push(i);
	}
	return ans;
	}
	};

view raw 84. Largest Rectangle in Histogram.cpp hosted with ❤ by GitHub