LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 用栈保存位置，如果新位置的高度比之前位置的都高则入栈，否则新位置入栈前要弹出所有比新位置高的位置。这样越靠近栈底的位置越低，计算栈中某个位置到栈顶位置的最大矩形面积时，靠近栈底的高度就是最大矩形的高度

 2 1 5 6 2 3
       _
     _| |
    | | |
    | | |  _
 _  | | |_| |
| |_| | | | |
| | | | | | |
0 1 2 3 4 5 6

heights[i] = 2 1 5 6 2 3 0 // 在末尾多添加一个0
i          = 0 1 2 3 4 5 6

i = 0
s = 0

i = 1 => heights[i] < heights[s.top()]
此时如果 1 入栈，则栈顶元素就不是最高的位置，因此要先将栈顶元素出栈
弹出栈顶元素 0，计算从 0 到 i 能形成的最大矩形面积，其高度就是 0 所在位置的高度
heights[0] * 1 = 2 * 1 = 2 => res = 2
计算结束再把 1 入栈
s = 1

i = 2，heights[i] > heights[s.top()]，入栈
s = 12

i = 3，heights[i] > heights[s.top()]，入栈
s = 123

i = 4 => heights[4] < heights[3]，heights[4] < heights[2]，弹出栈顶元素 3 和 2
计算 3 和 2 到 4 能形成的最大矩形面积
heights[3] * (4 - (2 + 1)) = 6 * 1 = 6 > 2 => res = 6
heights[2] * (4 - (1 + 1)) = 5 * 2 = 10 > 6 => res = 10
s = 14

i = 5，heights[i] > heights[s.top()]，入栈
s = 145

i = 6，heights[6] < heights[5]，heights[6] < heights[4]，heights[6] < heights[1]，弹出栈顶元素 541
计算 541 到 6 能形成的最大矩形面积
heights[5] * (6 - (4 + 1)) = 3 * 1 = 3 < 10 => res = 10
heights[4] * (6 - (1 + 1)) = 2 * 4 = 8 < 10 => res = 10
heights[1] * 6 = 1 * 6 = 6 < 10 => res = 10

i = 7 => 结束
res = 10

• 实现如下

class Solution {
 public:
  int largestRectangleArea(vector<int>& heights) {
    heights.emplace_back(0);
    stack<int> s;
    int res = 0;
    for (int i = 0; i < size(heights); ++i) {
      while (!empty(s) && heights[i] < heights[s.top()]) {
        int t = s.top();
        s.pop();
        res = max(res, heights[t] * (empty(s) ? i : (i - s.top() - 1)));
      }
      s.emplace(i);
    }
    return res;
  }
};