1、每日温度

739. 每日温度 - 力扣（LeetCode）

image.png

思路

暴力解法：

  1. class Solution {
  2. public:
  3.     vector<int> dailyTemperatures(vector<int>& temperatures) {
  4.         if(temperatures.size() == 1) return {0};
  5.         vector<int> result;
  6.         for(int i = 0; i < temperatures.size(); i++){
  7.             int count = 0;
  8.             for(int j = i + 1; j < temperatures.size(); j++){
  9.                 count++;
  10.                 if(temperatures[j] > temperatures[i]){
  11.                     result.push_back(count);
  12.                     break;
  13.                 }
  14.                 else if(j == temperatures.size() - 1){
  15.                     result.push_back(0);
  16.                 }
  17.             }
  18.         }
  19.         result.push_back(0);
  20.         return result;
  21.     }
  22. };

时间当然是超时了！

单调栈

三种情况：

  • 情况1：当前遍历的元素小于栈顶元素temperatures[ st.top( ) ]
  • 情况2：当前遍历的元素等于栈顶元素temperatures[ st.top( ) ]
  • 情况3：当前遍历的元素大于栈顶元素temperatures[ st.top( ) ]

当是情况 1 或者 2 的时候，将数组的下标入栈。如果是情况3，那么此时 i - st.top() 就是在第 i 天之后，才会有更高的温度，那么 result[ st.top() ] = i - st.top()；记录的就是 temperatures[ st.top() ] 在第 i 天之后才会有更高的温度。

不废话，直接上代码，如果看不懂，就去看卡哥的讲解，详细极了

  1. /*
  2.     情况1：当前遍历的元素小于栈顶元素temperatures[st.top()]
  3.     情况2：当前遍历的元素等于栈顶元素temperatures[st.top()]
  4.     情况3：当前遍历的元素大于栈顶元素temperatures[st.top()]
  5. */
  7. class Solution {
  8. public:
  9.     vector<int> dailyTemperatures(vector<int>& temperatures) {
  10.         if(temperatures.size() == 1) return {0};
  12.         stack<int> st;                                  // 递增栈
  13.         vector<int> result(temperatures.size(), 0);     // 存放结果
  14.         st.push(0);                                     // 将temperatures第一个元素的索引入栈
  15.         for(int i = 1; i < temperatures.size(); i++){
  16.             if(temperatures[i] < temperatures[st.top()]){           // 情况1
  17.                 st.push(i);
  18.             }
  19.             else if(temperatures[i] == temperatures[st.top()]){     // 情况2
  20.                 st.push(i);
  21.             }
  22.             else{                                                   // 情况3
  23.                 while(!st.empty() && temperatures[i] > temperatures[st.top()]){
  24.                     result[st.top()] = i - st.top();
  25.                     st.pop();
  26.                 }
  27.                 st.push(i);
  28.             }
  29.         }
  30.         return result;
  31.     }
  32. };

这些代码充分体现了解题逻辑，在完全理解之后，可以尝试对代码进行优化。

  1. /*
  2.     情况1：当前遍历的元素小于栈顶元素temperatures[st.top()]
  3.     情况2：当前遍历的元素等于栈顶元素temperatures[st.top()]
  4.     情况3：当前遍历的元素大于栈顶元素temperatures[st.top()]
  5. */
  7. class Solution {
  8. public:
  9.     vector<int> dailyTemperatures(vector<int>& temperatures) {
  10.         if(temperatures.size() == 1) return {0};
  12.         stack<int> st;                                  // 递增栈
  13.         vector<int> result(temperatures.size(), 0);     // 存放结果
  14.         st.push(0);                                     // 将temperatures第一个元素的索引入栈
  15.         for(int i = 1; i < temperatures.size(); i++){
  16.             while(!st.empty() && temperatures[i] > temperatures[st.top()]){     // 情况3
  17.                 result[st.top()] = i - st.top();
  18.                 st.pop();
  19.             }
  20.             st.push(i);                                 // 包含了情况1和情况2
  21.         }
  22.         return result;
  23.     }
  24. };
  • 时间复杂度O(n)
  • 空间复杂度O(n)

不建议一上来就写这种优化的代码，因为不能够体现出解题的逻辑性。

2、下一个更大元素 I

496. 下一个更大元素 I - 力扣（LeetCode）

image.png
image.png

接下来就要分析如下三种情况，一定要分析清楚。

  1. 情况一：当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况

此时满足递增栈（栈头到栈底的顺序），所以直接入栈。

  1. 情况二：当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况

如果相等的话，依然直接入栈，因为我们要求的是右边第一个比自己大的元素，而不是大于等于！

  1. 情况三：当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况

此时如果入栈就不满足递增栈了，这也是找到右边第一个比自己大的元素的时候。
判断栈顶元素是否在nums1里出现过，（注意栈里的元素是nums2的元素），如果出现过，开始记录结果。
记录结果这块逻辑有一点小绕，要清楚，此时栈顶元素在nums2中右面第一个大的元素是nums2[i]即当前遍历元素。

C++完整代码：

  1. /*
  2.     情况1：数组nums2当前元素小于上一个元素
  3.     情况2：数组nums2当前元素等于上一个元素
  4.     情况3：数组nums2当前元素大于上一个元素
  5. */
  7. class Solution {
  8. public:
  9.     vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
  10.         stack<int> st;      // 单调栈
  11.         vector<int> result(nums1.size(), -1);
  12.         unordered_map<int, int> umap;       // ket: 元素值，value：下标
  13.         for(int i = 0; i < nums1.size(); i++){
  14.             umap[nums1[i]] = i;
  15.         }
  16.         st.push(0);
  17.         for(int i = 1; i < nums2.size(); i++){      // 情况1
  18.             if(nums2[i] < nums2[st.top()]){
  19.                 st.push(i);
  20.             }
  21.             else if(nums2[i] == nums2[st.top()]){   // 情况2
  22.                 st.push(i);
  23.             }
  24.             else{                                   // 情况3
  25.                 while(!st.empty() && nums2[i] > nums2[st.top()]){
  26.                     if(umap.count(nums2[st.top()]) > 0){        // umap是否存在这个元素
  27.                         int index = umap[nums2[st.top()]];
  28.                         result[index] = nums2[i];
  29.                     }
  30.                     st.pop();
  31.                 }
  32.                 st.push(i);
  33.             }
  34.         }
  35.         return result;
  36.     }
  37. };

代码简化：

  1. /*
  2.     情况1：数组nums2当前元素小于上一个元素
  3.     情况2：数组nums2当前元素等于上一个元素
  4.     情况3：数组nums2当前元素大于上一个元素
  5. */
  7. class Solution {
  8. public:
  9.     vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
  10.         stack<int> st;      // 单调栈
  11.         vector<int> result(nums1.size(), -1);
  12.         unordered_map<int, int> umap;       // ket: 元素值，value：下标
  13.         for(int i = 0; i < nums1.size(); i++){
  14.             umap[nums1[i]] = i;
  15.         }
  16.         st.push(0);
  17.         for(int i = 1; i < nums2.size(); i++){
  18.             while(!st.empty() && nums2[i] > nums2[st.top()]){
  19.                     if(umap.count(nums2[st.top()]) > 0){            // umap是否存在这个元素
  20.                         result[umap[nums2[st.top()]]] = nums2[i];
  21.                     }
  22.                     st.pop();
  23.                 }
  24.                 st.push(i);
  25.         }
  26.         return result;
  27.     }
  28. };

3、下一个更大元素 II

503. 下一个更大元素 II - 力扣（LeetCode）

image.png

因为数组是一个环，那么要保证从头比较到尾，再从尾比较到头

  • 第一种方式是拼接数组，即将数组 nums 扩增两倍
  • 第二种方式是遍历两边数组 nums，可以不用去扩充nums

方式一：

  1. class Solution {
  2. public:
  3.     vector<int> nextGreaterElements(vector<int>& nums) {
  4.         // insert(pos, start, end);是insert重载的函数之一
  5.         // 在迭代器 pos 指定的位置之前，插入其他容器（不仅限于vector）中位于 [first,last) 区域的所有元素，
  6.         // 并返回表示第一个新插入元素位置的迭代器。
  7.         nums.insert(nums.end(), nums.begin(), nums.end());
  9.         // 开始单调栈
  10.         stack<int> st;
  11.         vector<int> result(nums.size(), -1);
  12.         st.push(0);
  13.         for(int i = 1; i < nums.size(); i++){
  14.             while(!st.empty() && nums[i] > nums[st.top()]){
  15.                 result[st.top()] = nums[i];
  16.                 st.pop();
  17.             }
  18.             st.push(i);
  19.         }
  20.         // 最后再把结果集即result数组resize到原数组大小
  21.         result.resize(nums.size() / 2);
  22.         return result;
  23.     }
  24. };

这种写法确实比较直观，但做了很多无用操作，例如修改了nums数组，而且最后还要把result数组resize回去。
resize倒是不费时间，是$O(1)$的操作，但扩充nums数组相当于多了一个$O(n)$的操作。

其实也可以不扩充nums，而是在遍历的过程中模拟走了两边nums。
代码如下：

  1. class Solution {
  2. public:
  3.     vector<int> nextGreaterElements(vector<int>& nums) {
  4.         // 其实也可以不扩充nums，而是在遍历的过程中模拟走了两遍nums。
  5.         vector<int> result(nums.size(), -1);
  6.         stack<int> st;
  7.         // 模拟走了两遍nums，1->2->3->4->3(第一遍)->1->2->3->4(第二遍)
  8.         // 注意，都是使用 i % nums.size() 来操作的
  9.         for(int i = 0; i < nums.size() * 2; i++){
  10.             while(!st.empty() && nums[i % nums.size()] > nums[st.top()]){
  11.                 result[st.top()] = nums[i % nums.size()];
  12.                 st.pop();
  13.             }
  14.             st.push(i % nums.size());
  15.         }
  16.         return result;
  17.     }
  18. };

4、接雨水

42. 接雨水 - 力扣（LeetCode）

image.png
image.png

思路

接雨水问题在面试中还是常见题目的，有必要好好讲一讲。
本文深度讲解如下三种方法：

  • 双指针法
  • 动态规划
  • 单调栈

双指针解法

这道题目使用双指针法并不简单，我们来看一下思路。
首先要明确，要按照行来计算，还是按照列来计算。

按照行来计算如图：
image.png

按照列来计算如图：

image.png
一些同学在实现的时候，很容易一会按照行来计算一会按照列来计算，这样就会越写越乱。
我个人倾向于按照列来计算，比较容易理解，接下来看一下按照列如何计算。
首先，如果按照列来计算的话，宽度一定是1了，我们再把每一列的雨水的高度求出来就可以了。
可以看出每一列雨水的高度，取决于，该列 左侧最高的柱子和右侧最高的柱子中最矮的那个柱子的高度。

这句话可以有点绕，来举一个理解，例如求列4的雨水高度，如图：
image.png
列4 左侧最高的柱子是列3，高度为2（以下用lHeight表示）。
列4 右侧最高的柱子是列7，高度为3（以下用rHeight表示）。
列4 柱子的高度为1（以下用height表示）
那么列4的雨水高度为 列3和列7的高度最小值减列4高度，即： min(lHeight, rHeight) - height。
列4的雨水高度求出来了，宽度为1，相乘就是列4的雨水体积了。
此时求出了列4的雨水体积。
一样的方法，只要从头遍历一遍所有的列，然后求出每一列雨水的体积，相加之后就是总雨水的体积了。
首先从头遍历所有的列，并且要注意第一个柱子和最后一个柱子不接雨水。

C++完整代码如下：

  1. class Solution {
  2. public:
  3.     int trap(vector<int>& height) {
  4.         int sum = 0;
  5.         for(int i = 0; i < height.size(); i++){
  6.             // 第一个柱子和最后一个柱子不能接雨水
  7.             if(i == 0 || i == height.size() - 1){
  8.                 continue;
  9.             }
  10.             int leftHeight = height[i];         // 当前柱子左边柱子的最大高度
  11.             int rightHeight = height[i];        // 当前柱子右边柱子的最大高度
  12.             for(int j = i - 1; j >= 0; j--){
  13.                 leftHeight = leftHeight > height[j] ? leftHeight : height[j];
  14.             }
  15.             for(int k = i + 1; k <= height.size() - 1; k++){
  16.                 rightHeight = rightHeight > height[k] ? rightHeight : height[k];
  17.             }
  18.             int h = min(leftHeight, rightHeight) - height[i];
  19.             if(h > 0){
  20.                 sum += h * 1;
  21.             }
  22.         }
  23.         return sum;
  24.     }
  25. };

因为每次遍历列的时候，还要向两边寻找最高的列，所以时间复杂度为$O(n^2)$。 空间复杂度为$O(1)$。
当然，双指针解法在LC上是超时了！

动态规划解法

在上一节的双指针解法中，我们可以看到只要记录左边柱子的最高高度 和 右边柱子的最高高度，就可以计算当前位置的雨水面积，这就是通过列来计算。

当前列雨水面积：min(左边柱子的最高高度，记录右边柱子的最高高度) - 当前柱子高度。
为了得到两边的最高高度，使用了双指针来遍历，每到一个柱子都向两边遍历一遍，这其实是有重复计算的。我们把每一个位置的左边最高高度记录在一个数组上（maxLeft），右边最高高度记录在一个数组上（maxRight）。这样就避免了重复计算，这就用到了动态规划。

当前位置，左边的最高高度是前一个位置的左边最高高度和本高度的最大值。
即从左向右遍历：maxLeft[i] = max(height[i], maxLeft[i - 1]);
从右向左遍历：maxRight[i] = max(height[i], maxRight[i + 1]);
这样就找到递推公式。

代码如下：

  1. class Solution {
  2. public:
  3.     int trap(vector<int>& height) {
  4.         int len = height.size();
  5.         if(len <= 2) return 0;
  6.         vector<int> maxLeft(len, 0);
  7.         vector<int> maxRight(len, 0);
  9.         // 记录每个柱子左边柱子最大高度
  10.         maxLeft[0] = height[0];
  11.         for(int i = 1; i < len; i++){
  12.             maxLeft[i] = max(height[i], maxLeft[i - 1]);
  13.         }
  14.         // 记录每个柱子右边最大高度
  15.         maxRight[len - 1] = height[len - 1];
  16.         for(int i = len - 2; i >= 0; i--){
  17.             maxRight[i] = max(height[i], maxRight[i + 1]);
  18.         }
  20.         int sum = 0;
  21.         for(int i = 0; i < len; i++){
  22.             int h = min(maxLeft[i], maxRight[i]) - height[i];
  23.             if(h > 0){
  24.                 sum += h * 1;
  25.             }
  26.         }
  27.         return sum;
  28.     }
  29. };

单调栈解法

这个解法可以说是最不好理解的了，所以下面我花了大量的篇幅来介绍这种方法。
单调栈就是保持栈内元素有序。和栈与队列：单调队列(opens new window)一样，需要我们自己维持顺序，没有现成的容器可以用。

准备工作

那么本题使用单调栈有如下几个问题：

  1. 首先单调栈是按照行方向来计算雨水，如图：

image.png
知道这一点，后面的就可以理解了。

  1. 使用单调栈内元素的顺序

从大到小还是从小到大呢？
从栈头（元素从栈头弹出）到栈底的顺序应该是从小到大的顺序。
因为一旦发现添加的柱子高度大于栈头元素了，此时就出现凹槽了，栈头元素就是凹槽底部的柱子，栈头第二个元素就是凹槽左边的柱子，而添加的元素就是凹槽右边的柱子。

如图：
image.png

  1. 遇到相同高度的柱子怎么办。

遇到相同的元素，更新栈内下标，就是将栈里元素（旧下标）弹出，将新元素（新下标）加入栈中。
例如 5 5 1 3 这种情况。如果添加第二个5的时候就应该将第一个5的下标弹出，把第二个5添加到栈中。
因为我们要求宽度的时候 如果遇到相同高度的柱子，需要使用最右边的柱子来计算宽度。
如图所示：
image.png

  1. 栈里要保存什么数值

是用单调栈，其实是通过 长 * 宽 来计算雨水面积的。
长就是通过柱子的高度来计算，宽是通过柱子之间的下标来计算，
那么栈里有没有必要存一个pair类型的元素，保存柱子的高度和下标呢。
其实不用，栈里就存放int类型的元素就行了，表示下标，想要知道对应的高度，通过height[stack.top()] 就知道弹出的下标对应的高度了。
所以栈的定义如下：

  1. stack<int> st; // 存着下标，计算的时候用下标对应的柱子高度

明确了如上几点，我们再来看处理逻辑。

单调栈处理逻辑

先将下标0的柱子加入到栈中，st.push(0);。
然后开始从下标1开始遍历所有的柱子，for (int i = 1; i < height.size(); i++)。
如果当前遍历的元素（柱子）高度小于栈顶元素的高度，就把这个元素加入栈中，因为栈里本来就要保持从小到大的顺序（从栈头到栈底）。
代码如下：

  1. if (height[i] < height[st.top()])  st.push(i);

如果当前遍历的元素（柱子）高度等于栈顶元素的高度，要跟更新栈顶元素，因为遇到相相同高度的柱子，需要使用最右边的柱子来计算宽度。
代码如下：

  1. if (height[i] == height[st.top()]) { // 例如 5 5 1 7 这种情况
  2.   st.pop();
  3.   st.push(i);
  4. }

如果当前遍历的元素（柱子）高度大于栈顶元素的高度，此时就出现凹槽了，如图所示：
image.png
取栈顶元素，将栈顶元素弹出，这个就是凹槽的底部，也就是中间位置，下标记为mid，对应的高度为height[mid]（就是图中的高度1）。
此时的栈顶元素st.top()，就是凹槽的左边位置，下标为st.top()，对应的高度为height[st.top()]（就是图中的高度2）。
当前遍历的元素i，就是凹槽右边的位置，下标为i，对应的高度为height[i]（就是图中的高度3）。

此时大家应该可以发现其实就是栈顶和栈顶的下一个元素以及要入栈的三个元素来接水！
那么雨水高度是 min(凹槽左边高度, 凹槽右边高度) - 凹槽底部高度，代码为：int h = min(height[st.top()], height[i]) - height[mid];
雨水的宽度是 凹槽右边的下标 - 凹槽左边的下标 - 1（因为只求中间宽度），代码为：int w = i - st.top() - 1 ;
当前凹槽雨水的体积就是：h * w。

求当前凹槽雨水的体积代码如下：

  1. while (!st.empty() && height[i] > height[st.top()]) { // 注意这里是while，持续跟新栈顶元素
  2.     int mid = st.top();
  3.     st.pop();
  4.     if (!st.empty()) {
  5.         int h = min(height[st.top()], height[i]) - height[mid];
  6.         int w = i - st.top() - 1; // 注意减一，只求中间宽度
  7.         sum += h * w;
  8.     }
  9. }

关键部分讲完了，整体代码如下：

  1. /*
  2.     单调栈的顺序是，从栈顶到栈底是从小到大的
  3.         情况1：当前柱子高度小于栈顶元素height[st.top()], st.push(i)
  4.         情况2：当前柱子高度等于栈顶元素height[st.top()], 先st.pop()，在st.push(i)
  5.         情况3：当前柱子高度大于栈顶元素height[st.top()], 说明出现凹槽
  6.                 3.1: int mid = st.top();
  7.                 3.2: st.pop()
  8.                 3.3: if(!st.empty()) 计算sum
  9.                 3.4: 满足 while(!st.empty() && height[i] > height[st.top()]) 重复上诉步骤
  10.                 3.5 st.push(i)
  11. */
  13. class Solution {
  14. public:
  15.     int trap(vector<int>& height) {
  16.         if(height.size() <= 2) return 0;        // 可以不加
  17.         stack<int> st;      // 存者下标，计算的时候，用数组对应的下标计算
  18.         st.push(0);
  19.         int sum = 0;
  20.         for(int i = 1; i < height.size(); i++){
  21.             if(height[i] < height[st.top()]){   // 情况1
  22.                 st.push(i);
  23.             }
  24.             if(height[i] == height[st.top()]){  // 情况2
  25.                 st.pop();                       // 其实这一句可以不加，效果是一样的，但处理相同的情况的思路却变了。
  26.                 st.push(i);
  27.             }
  28.             else{                               // 情况3
  29.                 while(!st.empty() && height[i] > height[st.top()]){     // 注意这里是while
  30.                     int mid = st.top();
  31.                     st.pop();
  32.                     if(!st.empty()){
  33.                         int h = min(height[i], height[st.top()]) - height[mid];
  34.                         int w = i - st.top() - 1;       // 注意减1，只求中间宽度
  35.                         sum += h * w;
  36.                     }
  37.                 }
  38.                 st.push(i);
  39.             }
  40.         }
  41.         return sum;
  42.     }
  43. };

代码可以精简，但是我觉得没什么必要。

5、柱状图中最大的矩形

84. 柱状图中最大的矩形 - 力扣（LeetCode）

image.png
image.png

思路

下标从 [i, j] 的矩形的最大面积，要么是 [i, j] 的最短的 height[k] w，要么是中间较长的 height[k] w；
如图所示：
image.png
再没有其他面积更大的可能性了。

双指针法

这道题跟上面的思路很相似，只不过，我们这里求的是当前 height[i] 两边比它小的 left 和 right

  1. class Solution {
  2. public:
  3.     int largestRectangleArea(vector<int>& heights) {
  4.         int sum = 0;
  5.         for(int i = 0; i < heights.size(); i++){
  6.             int left = i;
  7.             int right = i;
  8.             for(; left >= 0; left--){
  9.                 if(heights[left] < heights[i]) break;
  10.             }
  11.             for(; right < heights.size(); right++){
  12.                 if(heights[right] < heights[i]) break;
  13.             }
  14.             int h = heights[i];
  15.             int w = right - left - 1;       // 因为计算的是中间柱子，所以减一
  16.             sum = max(sum, h * w);
  17.         }
  18.         return sum;
  19.     }
  20. };

如上代码并不能通过leetcode，超时了，因为时间复杂度是$O(n^2)$。

动态规划

本题动态规划的写法整体思路和42. 接雨水(opens new window)是一致的，但要比42. 接雨水(opens new window)难一些。
难就难在本题要记录每个柱子 左边第一个小于该柱子的下标，而不是左边第一个小于该柱子的高度。
所以需要循环查找，也就是下面在寻找的过程中使用了while，详细请看下面注释，整理思路在题解：42. 接雨水(opens new window)中已经介绍了。

  1. class Solution {
  2. public:
  3.     int largestRectangleArea(vector<int>& heights) {
  4.         vector<int> minLeftIndex(heights.size());
  5.         vector<int> minRightIndex(heights.size());
  6.         int size = heights.size();
  8.         // 记录每个柱子，左边第一个小于当前柱子的下标
  9.         minLeftIndex[0] = -1;               // 注意这里的初始化，如果当前柱子i左边不存在小于它的柱子，那么minLeftIndex[i] = -1;这样是防止陷入死循环
  10.         for(int i = 1; i < heights.size(); i++){
  11.             int t = i - 1;
  12.             // 这里不是用if，而是需要不断向左寻找
  13.             while(t >= 0 && heights[t] >= heights[i]){
  14.                 t = minLeftIndex[t];
  15.             }
  16.             minLeftIndex[i] = t;
  17.         }
  19.         // 记录每个柱子，右边第一个小于当前柱子的下标
  20.         minRightIndex[size - 1] = size;     // 注意这里的初始化，如果当前柱子i右边不存在小于它的柱子，那么minRightIndex[i] = size，这样是防止陷入死循环
  21.         for(int i = size - 2; i >= 0; i--){
  22.             int t = i + 1;
  23.             // 这里不是用if，而是需要不断向右寻找
  24.             while(t < size && heights[t] >= heights[i]){
  25.                 t = minRightIndex[t];
  26.             }
  27.             minRightIndex[i] = t;
  28.         }
  30.         // 求最大面积
  31.         int sum = 0;
  32.         for(int i = 0; i < size; i++){
  33.             int w = minRightIndex[i] - minLeftIndex[i] - 1;
  34.             int h = heights[i];
  35.             int area = h * w;
  36.             sum = max(sum, area);
  37.         }
  38.         return sum;
  39.     }
  40. };

单调栈

本地单调栈的解法和接雨水的题目是遥相呼应的。
为什么这么说呢，42. 接雨水(opens new window)是找每个柱子左右两边第一个大于该柱子高度的柱子，而本题是找每个柱子左右两边第一个小于该柱子的柱子。
这里就涉及到了单调栈很重要的性质，就是单调栈里的顺序，是从小到大还是从大到小。
在题解42. 接雨水(opens new window)中我讲解了接雨水的单调栈从栈头（元素从栈头弹出）到栈底的顺序应该是从小到大的顺序。
那么因为本题是要找每个柱子左右两边第一个小于该柱子的柱子，所以从栈头（元素从栈头弹出）到栈底的顺序应该是从大到小的顺序！
我来举一个例子，如图：
image.png
只有栈里从大到小的顺序，才能保证栈顶元素找到左右两边第一个小于栈顶元素的柱子。
所以本题单调栈的顺序正好与接雨水反过来。
此时大家应该可以发现其实就是栈顶和栈顶的下一个元素以及要入栈的三个元素组成了我们要求最大面积的高度和宽度
理解这一点，对单调栈就掌握的比较到位了。
除了栈内元素顺序和接雨水不同，剩下的逻辑就都差不多了，在题解42. 接雨水(opens new window)我已经对单调栈的各个方面做了详细讲解，这里就不赘述了。
剩下就是分析清楚如下三种情况：

  • 情况一：当前遍历的元素heights[i]小于栈顶元素heights[st.top()]的情况
  • 情况二：当前遍历的元素heights[i]等于栈顶元素heights[st.top()]的情况
  • 情况三：当前遍历的元素heights[i]大于栈顶元素heights[st.top()]的情况

C++代码如下：

  1. /*
  2.     单调栈的顺序从栈顶到栈底是从大到小的，这样取出来的值才满足：小大小
  3.         情况1：下一个柱子的高度小于当前柱子
  4.         情况2：下一个柱子的高度等于当前柱子
  5.         情况3：下一个柱子的高度大于当前柱子
  6. */
  8. class Solution {
  9. public:
  10.     int largestRectangleArea(vector<int>& heights) {
  11.         int size = heights.size();
  12.         stack<int> st;
  13.         heights.insert(heights.begin(), 0); // 数组头部加入元素0
  14.         heights.push_back(0);               // 数组尾部加入元素0
  15.         st.push(0);
  16.         int sum = 0;
  17.         for(int i = 1; i < heights.size(); i++){
  18.             // 注意heights[i] 是和heights[st.top()] 比较 ，st.top()是下标
  19.             if(heights[i] > heights[st.top()]){
  20.                 st.push(i);
  21.             }
  22.             if(heights[i] == heights[st.top()]){
  23.                 st.pop();                   // 可以不加，也可以加，思路不同，但是这道题没有很大的不同
  24.                 st.push(i);
  25.             }
  26.             else{
  27.                 while(!st.empty() && heights[i] < heights[st.top()]){  // 注意是while
  28.                     int mid = st.top();
  29.                     st.pop();
  30.                     if(!st.empty()){
  31.                         int h = heights[mid];
  32.                         int w = i - st.top() - 1;
  33.                         sum = max(sum, h * w);
  34.                     }
  35.                 }
  36.                 st.push(i);
  37.             }
  38.         }
  39.         return sum;
  40.     }
  41. };

这里之所以要在头部和尾部加上0，是因为要求的是直方图最大矩形面积，而直方图最大矩形面积是肯定存在的，这一点跟接雨水不同，雨水有可能不存在（heights.size() <= 2时）。所以这道题需要从头开始求，因此给 heights 的头部和尾部都增加一个0，这样能够方便我们使用单调栈来求解。

一刷代码随想录总耗时
image.png
image.png