发现 LEETCODE上的思维题蛮有意思的
缺失的第一个正数(类似于求数组的mex)：将数组本身看成哈希表
class Solution { public int firstMissingPositive(int[] nums) { int n=nums.length,flag=0; for(int i=0;i<n;i++){ if(nums[i]==1)flag=1; } if(flag!=1)return 1;//数组里没有1 for(int i=0;i<n;i++){//把数组里[1,n]以外的数变为1 if(nums[i]<=0 || nums[i]>n)nums[i]=1; } for(int i=0;i<n;i++){//用nums[i]的正负来表示i出现过没有 int a=Math.abs(nums[i]); if(a==n)nums[0]=-Math.abs(nums[0]); else nums[a]=-Math.abs(nums[a]); } for(int i=1;i<n;i++){ if(nums[i]>0)return i; } if(nums[0]>0)return n; return n+1; } }
接雨水大合集
1.最普通版接雨水：维护左右两个指针向内扫描，每次移动的是高度低的那个，然后再维护左边最高值和右边最高值，统计贡献即可
class Solution { public: int trap(vector<int>& height) { if(height.size()==0)return 0; int sum=0,i=0,j=height.size()-1,lMax=height[0],rMax=height[j]; while(i<j){ if(height[i]<height[j]){ ++i; if(lMax<height[i])lMax=height[i]; sum+=lMax-height[i]; }else { --j; if(rMax<height[j])rMax=height[j]; sum+=rMax-height[j]; } } return sum; } };
2.二维接雨水：优先队列+bfs+单调性
我们先将最外面一圈方格拿出来，由于木桶理论，这圈方格内注水高度必定等于高度最低的那个格子
然后进行bfs拓展，每次取出高度最低的那个格子(i,j)，向其周围四个格子拓展
被拓展到的格子如果比(i,j)高，那么不能注水
被拓展到的格子比(i,j)低，那么可以注水，然后再将的高度变为(i,j)的高度(想想为什么)
用优先队列维护被拓展到的格子
class Solution { public: struct Node{ int i,j,h; Node(){} bool operator>(const Node a)const { return h>a.h; } }; int n,m,vis[200][200]; priority_queue<Node,vector<Node>,greater<Node> >pq; int trapRainWater(vector<vector<int>>& heightMap) { if(heightMap.size()==0)return 0; if(heightMap[0].size()==0)return 0; n=heightMap.size(); m=heightMap[0].size(); memset(vis,0,sizeof vis); for(int j=0;j<m;j++){ Node t; t.i=0,t.j=j,t.h=heightMap[0][j]; pq.push(t); t.i=n-1,t.j=j,t.h=heightMap[n-1][j]; pq.push(t); vis[0][j]=vis[n-1][j]=1; } for(int i=1;i<n-1;i++){ Node t; t.i=i,t.j=0,t.h=heightMap[i][0]; pq.push(t); t.i=i,t.j=m-1,t.h=heightMap[i][m-1]; pq.push(t); vis[i][0]=vis[i][m-1]=1; } int sum=0; while(pq.size()){ Node now=pq.top();pq.pop(); int i=now.i,j=now.j,h=now.h; sum+=h-heightMap[i][j]; //cout<<i<<" "<<j<<" "<<h<<"\n"; if(i-1>=0 && vis[i-1][j]==0){ Node t; t.i=i-1,t.j=j,t.h=max(h,heightMap[i-1][j]); pq.push(t); vis[i-1][j]=1; } if(i+1<n && vis[i+1][j]==0){ Node t; t.i=i+1,t.j=j,t.h=max(h,heightMap[i+1][j]); pq.push(t); vis[i+1][j]=1; } if(j-1>=0 && vis[i][j-1]==0){ Node t; t.i=i,t.j=j-1,t.h=max(h,heightMap[i][j-1]); pq.push(t); vis[i][j-1]=1; } if(j+1<m && vis[i][j+1]==0){ Node t; t.i=i,t.j=j+1,t.h=max(h,heightMap[i][j+1]); pq.push(t); vis[i][j+1]=1; } } return sum; } };
3.盛水最多的容器：贪心+双指针：和1差不多的做法，用贪心证明下就行
换个角度：总共有C(n,2)种选择方案，若每次移动长版，得到的面积只会比答案小，直接减掉这些移动长版的方案集，所以移动短板目的在于压缩选择方案集合
class Solution { public: int maxArea(vector<int>& height) { int i=0,j=height.size()-1; int ans=0; while(i<j){ ans=max(ans,min(height[i],height[j])*(j-i)); if(height[i]>height[j])--j; else ++i; } return ans; } };
原文：https://www.cnblogs.com/zsben991126/p/12862277.html
