容器盛水问题-栈解决方式
容器盛水问题
http://www.nowcoder.com/questionTerminal/31c1aed01b394f0b8b7734de0324e00f
这道题跟寻找一个数组中每个数后面的第一个比它大的数有相似之处，
都会自然想到用栈来解决，这道题的不同之处在于找到桶的边界。
首先整个数组的首尾肯定是桶的一个边界。因此我们从左往右边开始找
桶的边界，可以将桶分为以下几个情况：
a）5 1 1 1 1 6，桶左边界低
b）1 2 3 4 5 6，不能构成桶，桶边界递增
c）6 5 4 3 2 1，不能构成桶，桶边界递减
d）6 1 1 1 1 5，桶边界右边界低
数组的组成就是abcd这四种情况的随机组合，因此根据这几种桶的情
况，就可以利用栈来书写程序了
class Solution {
public:
long long maxWater(vector<int>& arr) {
//先找比之前元素大的，若没有找第二大的
//数组大小n，output为水滴数，定义一个栈pos存放“木板”长度
//，定义好栈和buck为桶的低边界的初始状态
int n=arr.size();
long long output(0);
stack<int> pos;
pos.push(arr[0]);
int buck(arr[0]);
//开始从左往右找，处理a，b两种桶的情况
for(int i=1;i<n;i++){
if(arr[i]<buck){
pos.push(arr[i]);
}
else
{
while(!pos.empty()){
output=buck-pos.top()+output;
pos.pop();
}
pos.push(arr[i]);
buck=arr[i];
}
}
//若栈不为空说明当前buck代表的左边界比右边界高
//逐个弹出栈中数据，处理cd两种状态下的桶
while(!pos.empty())
{
buck=pos.top();
pos.pop();
while(!pos.empty()&&pos.top()<buck)
{
output=buck-pos.top()+output;
pos.pop();
}
}
return output;
}
}; 
查看24道真题和解析
