接雨水
- 暴力法
直接记录左右最大,最后加上当前节点左右较小的与当前的差
func trap(height []int) int {
res:=0
if len(height)==0{
return 0
}
lmax:=make([]int,len(height))
rmax:=make([]int,len(height))
lmax[0]=height[0]
//保留左右每个节点对应方向的最大值
rmax[len(height)-1] = height[len(height)-1]
for i:=1;i<len(height);i++{
lmax[i] = max(lmax[i-1],height[i])
}
for i:=len(height)-2;i>=0;i--{
rmax[i] = max(rmax[i+1],height[i])
}
//节点i左右相对小的决定能盛多少水
for i:=0;i<len(height);i++{
res+=min(lmax[i],rmax[i])-height[i]
}
return res
}
func max(x,y int)int {
if x>y{
return x
}else{
return y
}
}
func min(x,y int)int {
if x>y{
return y
}else{
return x
}
}
- 左右指针
左右保留最大，left和right和相应方向的最大值比较
记录值
func trap(height []int) int {
res:=0
if len(height)==0{
return 0
}
//保留左右最大
lmax,rmax:=height[0],height[len(height)-1]
l,r:=0,len(height)-1
for l<=r{
lmax = max(lmax,height[l])
rmax = max(rmax,height[r])
if lmax>rmax{
res+= rmax-height[r] //不会为负数，因为是最大值
r--
}else{
res += lmax-height[l]
l++
}
}
return res
}
func max(x,y int)int {
if x>y{
return x
}else{
return y
}
}
- 单调栈
func maxWater( arr []int ) int64 {
// write code here
//单调栈 单调递减 存放下标 每次计算一层
if len(arr)==0{
return 0
}
res:=0
stack:=make([]int,0)
for i:=0;i<len(arr);i++{
for len(stack)!=0&&arr[stack[len(stack)-1]]<arr[i]{
s:=stack[len(stack)-1]
stack = stack[:len(stack)-1]
if len(stack)==0{ //前面没有则无法形成凹槽
break
}
//与前面相等可以跳过，也可以忽略
if arr[s]==arr[stack[len(stack)-1]]{
continue
}
w:=i-stack[len(stack)-1]-1
h:=min(arr[i],arr[stack[len(stack)-1]])-arr[s]
res+=w*h //计算面积 每层计算的方式
}
stack = append(stack,i)
}
return int64(res)
}
func min(x,y int)int{
if x>y{
return y
}else{
return x
}
}
84 柱状图中最大的矩形
方法一
方法二
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
if(heights.empty())
return 0;
//左右单调栈
vector<int>left(heights.size()),right(heights.size(),heights.size());
int sum = 0;
stack<int>sta;
for(int i=0;i<heights.size();i++)
{
while(!sta.empty()&&heights[sta.top()]>=heights[i])
{
right[sta.top()]=i;
sta.pop();
}
left[i] = sta.empty()?-1:sta.top();
sta.push(i);
}
for(int i=0;i<heights.size();i++)
{
sum = max(sum,heights[i]*(right[i]-left[i]-1));
}
return sum;
}
};