LC84: Largest Rectangle in Histogram

작성일

https://leetcode.com/problems/largest-rectangle-in-histogram/

  • 스택을 이용하는 간단한 문제. 높이는 주어진 vector에서 찾아서 쓰는 식으로 풀면 속도가 더 빨라진다.
  • 스택에서 가지는 필요없는 계산은 안한다는 아이디어로 생각해 보면
    • 현재 보고있는 막대보다 더 큰 막대가 스택의 꼭대기에 있다면, 그것은 뒤쪽에 나오는 막대와는 함께 쓸 수 없으므로
    • 스택 꼭대기 막대로 만들수 있는 최대 사각형 넓이를 계산하여, ans랑 비교해보고 스택에서 빼버린다.
  • 그렇다면 그 계산은 어떻게 이루어지냐면,
    • 스택에는 오름차순으로 막대가 존재할 수 밖에 없다.
    • 그러므로 스택꼭대기에 쌓인 두 막대 사이의 공간은 두 막대보다 높은 막대기들만 있었을것이다. (이미 고려해서 빠졌으므로)
    • 또 스택 꼭대기 막대와 현재 보고있는 막대 사이의 공간도에도, 두 막대보다 넓은 막대기만 있었을 것이다. (이미 고려해서 빠졌으므로)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
		stack<int> st;
		st.push(-1);
		heights.push_back(0);
		int ans = 0;
		for(int i = 0; i < heights.size(); i++) {
			while(st.size() > 1 && heights[st.top()] >= heights[i]) {
				int cur = st.top();
				st.pop();
				ans = max(ans, (i - st.top() - 1) * heights[cur]);
			}
			st.push(i);
		}
		return ans;
    }
};