栈和队列

用栈实现队列题目解析

用两个栈来维护，一个正序，一个逆序

class MyQueue {
    private LinkedList st1;
    private LinkedList st2;
    /** Initialize your data structure here. */
    public MyQueue() {
        st1 = new LinkedList<>();
        st2 = new LinkedList<>();
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        st1.addLast(x);
        LinkedList temp = new LinkedList<>(st1);
        st2.clear();
        while (!temp.isEmpty()) {
            st2.addLast(temp.removeLast());
        } 
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        int res =  st2.removeLast();
        LinkedList temp = new LinkedList<>(st2);
        st1.clear();
        while (!temp.isEmpty()) {
            st1.addLast(temp.removeLast());
        }
        return res;
    }
    
    /** Get the front element. */
    public int peek() {
        return st2.getLast();
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        if (st1.isEmpty()) return true;
        return false;
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

移掉K位数字题目解析

单调栈的经典题型（解析里四个题都看看）

class Solution {
    public String removeKdigits(String num, int k) {
        char[] nums = num.toCharArray();
        int size = nums.length - k;
        LinkedList stack = new LinkedList<>();
        stack.addLast('0');
        for (int i = 0; i < nums.length; i++) {
            while (stack.getLast() > nums[i] && nums.length - i > size - stack.size() + 1) {
                stack.removeLast();
            }
            if (stack.size() - 1 < size) {
                stack.addLast(nums[i]);
            }
        }
        StringBuilder sb = new StringBuilder();
        while(stack.size() > 1 && stack.getFirst() == '0') {
            stack.removeFirst();
        }
        while(!stack.isEmpty()) {
            sb.append(stack.removeFirst());
        }
        return sb.toString();
    }
}

柱状图中的最大矩形题目解析

先从中心扩散的方法做起

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

再看单调栈

class Solution {
    public int largestRectangleArea(int[] heights) {
        //单调栈和中间扩散的思想一致，栈尾与栈尾前一个数据的间隔里面的高度一定是大于栈尾的，
        //因为如果小于就会保留了。
        LinkedList stack = new LinkedList<>();
        int res = 0;
        stack.addLast(-1);
        for (int i = 0; i < heights.length; i++) {
            while (stack.size() != 1 && heights[stack.getLast()] > heights[i]) {
                int index = stack.removeLast();
                res = Math.max((i - stack.getLast() - 1) * heights[index], res);
            }
            stack.addLast(i);
        }
        while (stack.size() != 1) {
            int index = stack.removeLast();
            res = Math.max((heights.length - stack.getLast() - 1) * heights[index], res);
        }
        return res;
    }
}

顺便做一下最大矩形

接雨水题目解析

依然从中心扩散的思想开始

class Solution {
    public int trap(int[] height) {
        int res = 0;
        for (int i = 1; i < height.length - 1; i++) {
            int l = height[i], r = height[i];
            for (int j = 0; j < i; j++) {
                l = Math.max(l, height[j]);
            }
            for (int j = i + 1; j < height.length; j++) {
                r = Math.max(r, height[j]);
            }
            res += Math.min(l, r) - height[i];
        }
        return res;
    }
}

栈尾是中心，左右两边就是中心扩散要找到的双边。

class Solution {
    public int trap(int[] height) {
        LinkedList stack = new LinkedList<>();
        int res = 0;
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[stack.getLast()] < height[i]) {
                int index = stack.removeLast();
                if (!stack.isEmpty()) {
                    int left = stack.getLast(); 
                    res += (Math.min(height[i], height[left]) - height[index]) * (i - left - 1);
                }
            }
            stack.add(i);
        }
        return res;
    }
}

拼接最大数题目解析

就是两个单调栈，再从大到小合起来。看起来很复杂，但是逻辑一气呵成！

class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int[] res = new int[k];
        for (int i = 0; i <= k; i++) {
            if (i <= nums1.length && k - i <= nums2.length) {
                int[] temp = merge(nums1, nums2, i, k - i);
                for (int j = 0; j < k; j++) {
                    if (compare(res, temp, 0, 0)) {
                        res = Arrays.copyOf(temp, k);
                    }
                }
            }
        }
        return res;
    }
    private int[] merge(int[] nums1, int[] nums2, int n1, int n2) {
        int[] a1 = builder(nums1, n1);
        int[] a2 = builder(nums2, n2);
        int[] res = new int[n1 + n2];
        int index1 = 0, index2 = 0;
        while (index1 < n1 && index2 < n2) {
            if (compare(a1, a2, index1, index2)) {
                res[index1 + index2] = a2[index2];
                index2++;
            } else {
                res[index1 + index2] = a1[index1];
                index1++;
            }
        } 
        while (index1 < n1) {
            res[index1 + index2] = a1[index1];
            index1++;
        }
        while (index2 < n2) {
            res[index1 + index2] = a2[index2];
            index2++;
        }
        return res;
    }
    private int[] builder(int[] nums, int n) {
        LinkedList stack = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[stack.getLast()] < nums[i] && stack.size() + nums.length - i > n) {
                stack.removeLast();
            }
            stack.addLast(i);
        }
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = nums[stack.removeFirst()];
        }
        return res;
    }
    private boolean compare(int[] nums1, int[] nums2, int index1, int index2) { //小于?
        while (index1 < nums1.length && index2 < nums2.length) {
            if (nums1[index1] == nums2[index2]) {
                index1++;
                index2++;
            } else if (nums1[index1] < nums2[index2]) {
                return true;
            } else return false;
        }
        return index1 == nums1.length;
    }
}

滑动窗口的最大值题目解析

单调队列。用双向队列，保持队列从大到小单调性，如果开头的数据移除窗口就出列。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        LinkedList queue = new LinkedList<>();
        int[] res = new int[nums.length-k+1];
        for (int i = 0; i < nums.length; i++) {
            while (!queue.isEmpty() && nums[queue.getLast()] <= nums[i]) {
                queue.removeLast();
            }
            queue.addLast(i);
            if (i >= k-1) {
                res[i-k+1] = nums[queue.getFirst()];
                if (i-k+1 == queue.getFirst()) queue.removeFirst();
            }
        }
        return res;
    }
}

栈和队列

相关

标签