题目：
给定 nn 个非负整数表示每个宽度为 11 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
例如，当给定数字序列为 0,1,0,2,1,0,1,3,2,1,2,1 时，柱子高度图如下所示，最多可以接 66 个单位的雨水。
输入格式
第一行包含整数 nn。
第二行包含 nn 个非负整数。
输出格式
输出一个整数，表示最大接水量。
数据范围
1≤n≤1051≤n≤105,
序列中元素均不大于 10001000。
输入样例：
1. 12 2. 0 1 0 2 1 0 1 3 2 1 2
输出样例：
6
方法一：单调栈
思路：维护一个单调递减的栈，一旦遇到一个大于栈头的柱子，就进行接水，否则对于小于栈头的柱子就行入栈，能够进行接水时对于小于目前柱子的栈的下标，全部清除。
倘若清除完毕后，栈为空，则直接进行下一轮，我们利用长*宽来求次柱子的接水量
宽：i - s.top() -1 i代表接水量柱子的左侧，s.top代表接水量柱子的右侧
高：a[i] - a[s.top()]代表接水量柱子的高
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<stack> using namespace std; const int N = 1000010; int a[N]; stack<int>s; int main(){ cin.tie(0); ios::sync_with_stdio(false); int n; cin>>n; int res = 0; for(int i = 0;i < n;i++)cin>>a[i]; for(int i = 0;i < n;i++){ //倘若目前的柱子大于栈头的柱子，则要进行接水 while(!s.empty() && a[i] > a[s.top()]){ //首先出栈的一定是左右两个柱子中，最低的部分，也就是可以进行接雨水的部分 int t = s.top(); s.pop(); if(s.empty())break; else{ int h = min(a[s.top()],a[i]) - a[t];//计算高度 int w = i - s.top() -1;//计算宽度 res += h * w;//记录接水量 } } s.push(i);//对于满足单调栈的柱子进行入队 } cout<<res<<endl; return 0; }
方法二：双指针
双指针，从左和右出发两个指针，每次记录左右两侧最大值，lm为[1,l]最大值，rm为[r,n]最大值,每次从最大值小的那一方开始收水，比如lm < rm,可以收l的水，因为l左侧[1,l]最大值确定，右侧[l,n]有值大于左侧最大值,反之亦然。
一列一列收水，一次收完一列水
#include<bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int n, h[N], res; int main() { cin >> n; for(int i = 0; i < n; i ++) cin >> h[i]; int l = 0, r = n - 1; int lm = 0, rm = 0; while(l < r) { lm = max(h[l], lm); rm = max(h[r], rm); if(h[l] < rm) res += lm - h[l ++]; else res += rm - h[r --]; } cout << res; return 0; }
