栈的运用——《挑战程序设计竞赛》

POJ 2559: Largest Rectangle in a Histogram

给定从左到右n个矩形，已知这此矩形的宽度都为1，长度不完全相等，为$h_1,h_2, \cdots, h_n$。这些矩形相连排成一排，求在这些矩形包括的范围内能得到的面积最大的矩形，打印出该面积。所求矩形可以横跨多个矩形，但不能超出原有矩形所确定的范围。
$1\le n \le 100000$
输入
7 2 1 4 5 1 3 3
输出
8

从微软面试时学到的道理，拿到一个题目想想出最简单的算法，并能让这个算法能够成功地work。首先如果确定了长方形的左端点L和右端点R，那么最大可能的高度就是 $\min \{ h_i | L \le i <R \}$ 。这样我们遍历L和R，在$[L,R)$中找最小的$h_i$这样naive的算法是$O(n^3)$的复杂度。对于区间的最小值做优化，比如说用尺取法那么就可以把复杂度降为$O(n^2)$。即使这样还是不能满足这道题的数据范围。

假设最大的长方形的左端是L，右端是R（左闭右开），高度是H，那么一定有 $h_{L-1} <H$ 和$h_R<H$，并且高度 $H = \min \{h_i | L \le i < R \}$ 。因此，我们可以每次固定i，找到L和R，最后再遍历一遍找到$(R-L)\times H$的最大值。即我们维护两个数组L[i]和R[i],

L[i] 是从i向左找，找到第一个小于h[i]的index，而后将这个index+1的值
R[i]是从i向右找，找到第一个小于h[i]的index （因为右边是开的，所以这个index不用减一）

使用单调栈可以非常高效地求解这个问题。考虑计算L的情况。首先定义一个栈，并且将它初始化为空，然后不断增加i的值，并维护这个栈使它按照下面的顺序存储用于推算后面L值的元素：

设在栈里的元素从上到下的值为 $x_i$ ，则 $x_i > x_{i+1}$ 且 $h_{x_i} > h_{x_{i+1}}$
也就是维护一个单调栈，维护一个单调栈的作用是，每次在计算L[i]时，我们实现看栈顶的元素j，如果j满足$h_j \ge h_i$，则不断取出栈顶元素（因为我们要找到第一个小于h[i]的index）；如果栈为空，说明找到头也没找到，那么L[i]=0，如果$h_j < h_i$，则L[i]=j+1。然后把i压入栈中。

由于栈的压入和弹出操作都是$O(n)$次，因此这个算法的复杂度就是$O(n)$，对于R[i]也可以用同样的方法计算。题解代码如下：

#include<iostream>
#include<stack>
#include<stdio.h>

using namespace std;

int h[100010];
int L[100010], R[100010];
int main()
{
    int n;
    while(scanf("%d",&n)!= EOF && n)
    {
       for(int i=0;i<n;i++)
       {
           cin>>h[i];
       }
       stack<int> left;
       for(int i=0;i<n;i++)
       {
           while(!left.empty() && h[left.top()]>=h[i]) left.pop();
           L[i] = left.empty()? 0 : (left.top() + 1);
           left.push(i);
       }
       stack<int> right;
       for(int i=n-1;i>=0;i--)
       {
           while(!right.empty() && h[right.top()]>=h[i]) right.pop();
           R[i] = right.empty()? n : (right.top());
           right.push(i);
       }

       long long res = 0;
       for(int i=0;i<n;i++)
       {
           res = max(res,(long long)(R[i] - L[i])*h[i]);
       }
       cout<<res<<endl;
    }
    return 0;
}

接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

因为要积水，来自于不少于两个柱子之间的高度关系。我们在遍历数组时维护一个栈。如果当前的柱子的高度小于或等于栈顶的柱子，我们将柱子的索引入栈，意思是当前这个柱子被栈中的前一个柱子界定。如果我们发现一个柱子的高度大于栈顶的柱子，我们可以确定栈顶的柱子被当前柱子和栈顶的前一个柱子界定，因此我们可以弹出栈顶元素，并且累加由当前柱子和栈顶的前一个柱子贡献出来的积水（当前柱子和栈顶柱子的高度差乘以当前柱子和栈顶的前一个柱子的宽度）到 ans ，直到栈为空或栈顶柱子不低于当前柱子，随后把当前柱子的索引入栈。

这样的做法与上述的POJ2559题目的想法有异曲同工之妙。同样是维护了一个单调栈，栈中元素上到下，对应的高度递增，像一个金字塔形。代码如下：

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> right;
        int ans = 0;
        for(int i=0;i<height.size();i++)
        {
            while(!right.empty() && height[right.top()]<height[i]) 
            {
                int top = height[right.top()];
                right.pop();
                if(right.empty())break;
                ans += ((min(height[right.top()],height[i])-top) * (i-right.top()-1));
            }
            right.push(i);
        }
        return ans;
    }
};

盛水最多的容器

给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

因为与上两题比较类似，我把这道题列在这儿。

要想围住的面积最大，需要尽量保证

底边长比较大（两数在数组中的距离较远）
两数的最小值比较大
为了达到这两个目标，我们从底边长较大开始，定义两个变量 i，j 来记录两数的位置，并将其初始值置为 0 和 size-1。虽然此时底边长度最大，但由于这两条边可能都比较短，此时的面积很可能不是最大面积。现在的任务便是如何缩小底边的同时尽量获得最大的边长。

不妨设此时两边边长不等，倘若将长的那一边移进，显然新的面积恒小于当前面积（因为限制当前面积的不是这条长的边，新的面积的底边长缩小，竖直边长不大于原边长）；因此要想获得更大的面积，只能移进那条较短的边。

按照这个思路，不断移进短的边，直到 i 和 j 相等，在移进的过程中记录最大边长即可。代码如下：

class Solution {
public:
    int maxArea(vector<int>& height) {
        vector<int>::iterator head=height.begin();
        vector<int>::iterator tail=height.end()-1;
        int maxVoil = 0;
        while(head!=tail)
        {
            int area = (tail - head) * ((*head<*tail)? *head:*tail);
            maxVoil = maxVoil>area?maxVoil:area;
            if(*head < *tail) head++;
            else tail--;
        }
        return maxVoil;
    }
};