力扣热题8-荷兰旗、柱状图最大矩形


按照leetcode刷一遍:leetcode hot

75. 颜色分类(再看看)

荷兰旗问题:

image-20220221103926736

计数排序-两次扫描

class Solution {
    public void sortColors(int[] nums) {
        int redCount = 0;
        int whiteCount = 0;
        int blueCount = 0;
        int n = nums.length;
        for(int i=0;i<n;i++) {
            if(nums[i]==0) redCount++;
            else if(nums[i]==1) whiteCount++;
            else blueCount++;
        }
        int idx = 0;
        for(int i=0;i<redCount;i++) nums[idx++] = 0;
        for(int i=0;i<whiteCount;i++) nums[idx++] = 1;
        for(int i=0;i<blueCount;i++) nums[idx++] = 2;
    }
}

进阶:

你能想出一个仅使用常数空间的一趟扫描算法吗?

双指针

class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        if(n<=1) {
            return;
        }
        // [0,p0) 0
        // [p0,i) 1
        // (p2,n-1) 2
        int p0 = 0;
        int p2 = n-1;
        int i = 0;
        while(i<=p2) {
            if(nums[i]==0) {
                swap(nums,p0,i);
                p0++;
                i++;
            } else if(nums[i]==1) {
                i++;
            } else {
                // nums[i]==2
                swap(nums,p2,i);
                p2--;
            }
            System.out.println(Arrays.toString(nums));
        }
    }

    private void swap(int[] nums,int i,int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

76. 最小覆盖子串

过了,但是比较丑陋。滑窗思想没错,就这样

class Solution {
    public String minWindow(String s, String t) {
        int[] scount = new int[128];
        int[] tcount = new int[128];
        if(s.length()<t.length()) {
            return "";
        }
        for(int i=0;i<t.length();i++) {
            tcount[t.charAt(i)]++;
        }
        int tCharCount = 0;
        for(int i=0;i<128;i++) {
            if(tcount[i]!=0) tCharCount++;
        }

        int readyCharCount = 0;
        int finalLeft = -1;
        int finalRight = s.length();
        int left = 0;
        int i=0;
        for(i=0;i<s.length();i++) {
            int p = (int)s.charAt(i);
            scount[p]++;
            if(scount[p]==tcount[p]) {
                readyCharCount++;
            }
            if(readyCharCount==tCharCount&&i-left<finalRight-finalLeft) {
                finalRight = i;
                finalLeft = left;
                break;
            }
        }
        if(i==s.length()) return "";
        // 方便去除left
        scount[s.charAt(i)]--;
        for(;i<s.length();i++) {
            int p = (int)s.charAt(i);
            scount[p]++;
            while(left<i) {
                int leftc = (int)s.charAt(left);
                if(scount[leftc]>tcount[leftc]) {
                    scount[leftc]--;
                    left++;
                } else {
                    break;
                }
            }
            //System.out.println(s.substring(left,i+1));
            if(i-left<finalRight-finalLeft) {
                finalRight = i;
                finalLeft = left;
            }
        }
        return finalLeft==-1?"":s.substring(finalLeft,finalRight+1);
    }
}

78. 子集

递归

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Deque<Integer> deque = new LinkedList<>();
        subsetsHelper(nums,result,deque,0);
        return result;
    }

    private void subsetsHelper(int[] nums,List<List<Integer>> result,Deque<Integer> deque,int start) {
        if(start==nums.length) {
            result.add(new ArrayList(deque));
            return;
        }
        subsetsHelper(nums,result,deque,start+1);
        deque.addLast(nums[start]);
        subsetsHelper(nums,result,deque,start+1);
        deque.removeLast();
    }
}

79. 单词搜索

回溯

class Solution {
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        boolean[][] visited = new boolean[m][n];
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                if(search(board,word,i,j,0,visited)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean search(char[][] board,String word,int i,int j,int idx,boolean[][] visited) {
        if(idx==word.length()) return true;
        if(i<0||j<0||i>=board.length||j>=board[0].length||
                visited[i][j]||
                board[i][j]!=word.charAt(idx))  {
            return false;
        }
        visited[i][j] = true;
        boolean result = search(board,word,i+1,j,idx+1,visited)||
                    search(board,word,i,j+1,idx+1,visited)||
                    search(board,word,i-1,j,idx+1,visited)||
                    search(board,word,i,j-1,idx+1,visited);
        visited[i][j] = false;
        return result;
    }
}

84. 柱状图中最大的矩形(再看看)

双边扩展-超时

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int left = 0;
        int right = 0;
        int result = 0;
        for(int i=0;i<n;i++) {
            left = right = i;
            while(left-1>=0&&heights[left-1]>=heights[i]) {
                left--;
            }
            while(right+1<n&&heights[right+1]>=heights[i]) {
                right++;
            }
            result = Math.max(result,heights[i]*(right-left+1));
        }
        return result;
    }
}

前后两个单调栈

我还挺牛逼,这个方法过了,除了效率有点低。

image-20220221153937634

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] result = new int[n];
        // 前后两个单调队列
        Stack<Integer> lrStack = new Stack<>();
        lrStack.add(0);
        for(int i=1;i<n;i++) {
            if(lrStack.isEmpty()||heights[i]>=heights[lrStack.peek()]) {
                lrStack.add(i);
            } else {
                while(!lrStack.isEmpty()&&heights[lrStack.peek()]>heights[i]) {
                    int p = lrStack.peek();
                    result[p] = (i-p)*heights[p];
                    lrStack.pop();
                }
                lrStack.add(i);
            }
        }
        if(!lrStack.isEmpty()) {
            while(!lrStack.isEmpty()) {
                int p = lrStack.peek();
                result[p] = (n-p)*heights[p];
                lrStack.pop();
            }
        }

        Stack<Integer> rlStack = new Stack<>();
        rlStack.add(n-1);
        for(int i=n-2;i>=0;i--) {
            if(rlStack.isEmpty()||heights[i]>=heights[rlStack.peek()]) {
                rlStack.add(i);
            } else {
                while(!rlStack.isEmpty()&&heights[rlStack.peek()]>heights[i]) {
                    int p = rlStack.peek();
                    result[p] += (p-i)*heights[p];
                    rlStack.pop();
                }
                rlStack.add(i);
            }
        }
        if(!rlStack.isEmpty()) {
            while(!rlStack.isEmpty()) {
                int p = rlStack.peek();
                result[p] += (p+1)*heights[p];
                rlStack.pop();
            }
        }

        int res = 0;
        for(int i =0;i<n;i++) {
            res = Math.max(res,result[i]-heights[i]);
        }
        return res;
    }
}

一个单调栈

两个单调栈复杂了,一个就可以了。注意单调栈第一个可以算到最开始位置,其他都会被peek拦住。

image-20220221154642594

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int result = 0;
        Stack<Integer> lrStack = new Stack<>();
        for(int i=0;i<n;i++) {
            while(!lrStack.isEmpty()&&heights[lrStack.peek()]>heights[i]) {
                int p = lrStack.pop();
                result = Math.max(result,lrStack.isEmpty()?i*heights[p]:(i-lrStack.peek()-1)*heights[p]);
            }
            lrStack.add(i);
        }
        if(!lrStack.isEmpty()) {
            while(!lrStack.isEmpty()) {
                int p = lrStack.pop();
                result = Math.max(result,lrStack.isEmpty()?n*heights[p]:(n-lrStack.peek()-1)*heights[p]);
            }
        }
        return result;
    }
}

奇怪,为啥效率这么低。

image-20220221161610654

不改算法,只是Stack换成Deque就快了很多:

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int result = 0;
        Deque<Integer> lrStack = new LinkedList<>();
        for(int i=0;i<n;i++) {
            while(!lrStack.isEmpty()&&heights[lrStack.peekLast()]>heights[i]) {
                int p = lrStack.pollLast();
                result = Math.max(result,lrStack.isEmpty()?i*heights[p]:(i-lrStack.peekLast()-1)*heights[p]);
            }
            lrStack.addLast(i);
        }
        if(!lrStack.isEmpty()) {
            while(!lrStack.isEmpty()) {
                int p = lrStack.pollLast();
                result = Math.max(result,lrStack.isEmpty()?n*heights[p]:(n-lrStack.peekLast()-1)*heights[p]);
            }
        }
        return result;
    }
}

原因

image-20220221162332866

Stack继承自VectorVector很多方法用synchronized保证线程安全,效率不大行。