（以下序号都是leetcode原题）

单调栈

503 739

对于单调栈一直有心理阴影（之前有一个场景很复杂的单调栈给我吓坏了），这次写总结的时候刚刚又写了一遍，当我们求一个单调答案集的时候，由于求其中某个答案可能对后面有一定的剩余价值，就需要类似单调栈的结构。

public int[] nextGreaterElements(int[] nums) {
        int[]ans=new int[nums.length];
        Arrays.fill(ans,-1);
        Deque<Integer> shuangxiangzhan=new ArrayDeque<Integer>();
        shuangxiangzhan.offerFirst(0);
        for(int i=1;i<2*nums.length;i++){
            int j=i%nums.length;
            while(!shuangxiangzhan.isEmpty()&&nums[shuangxiangzhan.peekLast()]<nums[j]){
                int hasAns=shuangxiangzhan.pollLast();
                ans[hasAns]=nums[j];
            }
            shuangxiangzhan.offerLast(j);
        }
        return ans;
    }

739其实和503一模一样 只是最后的结果减一下下标就可以了。

public int[] dailyTemperatures(int[] nums)  {
        int[]ans=new int[nums.length];
        Arrays.fill(ans,0);
        Deque<Integer> shuangxiangzhan=new ArrayDeque<Integer>();
        shuangxiangzhan.offerFirst(0);
        for(int i=1;i<nums.length;i++){
            int j=i%nums.length;
            while(!shuangxiangzhan.isEmpty()&&nums[shuangxiangzhan.peekLast()]<nums[j]){
                int hasAns=shuangxiangzhan.pollLast();
                ans[hasAns]=j-hasAns;
            }
            shuangxiangzhan.offerLast(j);
        }
        return ans;
    }

并查集

547 684 200

547可以用并查集 深搜 宽搜等 并查集还要慢一点。。。

public int findCircleNum(int[][] isConnected) {
        int n=isConnected.length;
        int []root=new int[n];
        for(int i=0;i<n;i++)root[i]=i;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(isConnected[i][j]==1){
                    root[findFather(i,root)]=findFather(j,root);
                }
            }
        }
        int ans=0;
        for(int i=0;i<n;i++){
            if(root[i]==i)ans++;
        }
        return ans;
    }

    private int findFather(int j, int[] root) {
        while(root[j]!=j)j=root[j];
        return j;
    }

684删除冗余那条边 就不断搞并查集或者搜索直到访问的边的两点已经在某个集合中就好咯，这次用搜索写一下子把，深搜吧（好写）

//纯属扯淡，这题搜索太麻烦了，搜索合起来点的话就容易把前面的当第一个是冗余的边，就算给边再排个序也要在中途判断是不是已经冗余了 

这里突然想搞个路径压缩并查集，忘了咋合并两个树了....

public int[] findRedundantConnection(int[][] edges) {
        int n=edges.length;
        int[]v=new int[n+1];
        int[]root=new int[n+1];
        for(int i=0;i<root.length;i++)root[i]=i;
        for(int[]edge:edges){
            int l,r;
            l=edge[0];
            r=edge[1];
            if(getRoot(l,root)==getRoot(r,root))return edge;
            root[getRoot(l,root)]=getRoot(r,root);
        }
        return new int[]{0,0};
    }
    private int getRoot(int l,int[]root){
        if(root[l]!=l)root[l]=getRoot(root[l],root);
        return root[l];
    }

200岛屿数量

这个玩意儿竟然还能并查集做？？？？有点太强行了，这里我三种方法都写一下，就当准备明天的考试了 

这个玩意儿怎么会这么慢呢，有点疑惑

public int numIslands(char[][] grid) {
        int ans=0;
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(grid[i][j]=='1'){
                    ans++;
                    dfs(grid,i,j);
                }
            }
        }
        return ans;
    }
    void dfs(char[][]grid,int row,int col){
        int[][]offset={{1,0},{-1,0},{0,1},{0,-1}};
        grid[row][col]='0';
        for(int i=0;i<4;i++){
            int newrow=row+offset[i][0];
            int newcol=col+offset[i][1];
            if(newrow<0||newrow>=grid.length||newcol<0||newcol>=grid[0].length)continue;
                if(grid[newrow][newcol]=='1')dfs(grid,row+offset[i][0],col+offset[i][1]);
            
        }
    }

再整个bfs的写法，这里强烈不推荐这么搞，建一个内部类不比搁这用Map.entry来的舒适简单？（仅仅针对我这种菜鸟）

public int numIslands(char[][] grid) {
        int ans=0;
        int [][]offset={{0,1},{0,-1},{1,0},{-1,0}};
        ArrayDeque<Map.Entry<Integer,Integer>> queue=new ArrayDeque<>();
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(grid[i][j]=='1'){
                    ans++;
                    HashMap<Integer,Integer>tempmap=new HashMap<>();
                    tempmap.put(i,j);
                    queue.addFirst((Map.Entry<Integer,Integer>)tempmap.entrySet().toArray()[0]);
                    while(!queue.isEmpty()){
                        Map.Entry<Integer,Integer>head=queue.poll();
                        int row=head.getKey();
                        int col=head.getValue();
                        grid[row][col]='0';
                        for(int k=0;k<4;k++){
                            int newrow=row+offset[k][0];
                            int newcol=col+offset[k][1];
                            if(newrow<0||newrow>=grid.length||newcol<0||newcol>=grid[0].length)continue;
                            if(grid[row+offset[k][0]][col+offset[k][1]]=='1'){
                                tempmap.clear();
                                tempmap.put(row+offset[k][0],col+offset[k][1]);
                                queue.addFirst((Map.Entry<Integer,Integer>)tempmap.entrySet().toArray()[0]);
                            }
                        }
                    }
                }
            }
        }
        return ans;
    }

题解里还有个巨离谱的并查集方法，立个flag，之后在这里写一遍，手勤快才能学到东西。

滑动窗口

1208

1208尽可能使字符串相等，注意是对应位置的啊！！！！！！直接滑动窗口维护cost小于target就好，这里有写的技巧，滑动窗口应该是找到一个合适的（伸），前面缩小（缩），直到不符合，然后就是一些限制条件和更新结果值。

前缀和

560

这个破玩意儿要找的是个数 前面可能有多个 （0或者负数那种符合的） 注意一开始还得加个0代表从头开始的前缀和为0的情况，

杂题：

358K距离重排字符串

这个题啊，看着简单，写起来也简单，就是有点不熟练，给一个字符串和距离，问你能不能重排字符串让每俩相同的字符距离都>=给的距离

拿到题就觉得，对每个字符按数量排序，最多的先插完，看别的能不能补了空。但是返回的是字符串，维护许许多多的index目前看来貌似是有点愚蠢而且不可实现的。

题解的想法其实有相似之处，维护按数目排序的char，然后每次在暂存队列中轮番取出来连接成字符串，够了就走（我一开始看了题解大意写的是每次都用这几个最少的那个先连完，这样是不对的，考虑444422  5的情况，不管能不能连成功，如果一开始尽力使用完前五个进入队列的，剩下那个2很有可能就完不成了。另外，每次都将五个推出来用掉一个放回去重排序会超时！）