有效的括号


解法:压栈出栈

public class Solution {
    public boolean isValid(String s) {

        Deque<Character> deque = new LinkedList<>();
        Map<Character, Character> map = new HashMap<>();
        map.put(')', '(');
        map.put(']', '[');
        map.put('}', '{');

        for (char c : s.toCharArray()) {
            if (deque.isEmpty() || deque.peekFirst() != map.get(c)) {
                deque.offerFirst(c);
            } else {
                deque.pollFirst();
            }
        }
        return deque.isEmpty();
    }

    public static void main(String[] args) {
        boolean valid = new Solution().isValid("()[]][");
        System.out.println(valid);
    }
}

最小栈


思路:

  • 运用两个栈,维护一个值栈和一个最小值栈
  • 入栈时判断值是否大于最小值栈栈顶,如果大于等于就复制一个栈顶元素到栈顶
  • 如果入栈元素小于最小值栈顶,加入最小值栈
class MinStack {

   Deque<Integer> deque;
    Deque<Integer> minDeque;

    /** * initialize your data structure here. */
    public MinStack() {
        //值栈
        deque = new LinkedList<>();
        //最小值栈
        minDeque = new LinkedList<>();
    }

    public void push(int x) {
        //入值栈
        deque.offerFirst(x);
        //如果x小于最小值栈顶,就如最小值栈
        if (minDeque.isEmpty() || minDeque.peekFirst() >= x) {
            minDeque.offerFirst(x);
        } else {
            //如果最小值栈数小于x,就拷贝一份最小值在栈顶
            minDeque.offerFirst(minDeque.peekFirst());
        }
    }

    public void pop() {
        deque.pollFirst();
        minDeque.pollFirst();
    }
    public int top() {
        return deque.peekFirst();
    }
    public int getMin() {
        return minDeque.peekFirst();
    }
}

用栈实现队列

class MyQueue {

    Stack<Integer> in;
    Stack<Integer> out;

    /** * Initialize your data structure here. */
    public MyQueue() {
        in = new Stack<>();
        out = new Stack<>();
    }

    /** * Push element x to the back of queue. */
    public void push(int x) {
        in.push(x);
    }

    /** * Removes the element from in front of queue and returns that element. */
    public int pop() {
        if (out.isEmpty()) {
            while (!in.isEmpty()) {
                out.push(in.pop());
            }
        }
        return out.pop();
    }

    /** * Get the front element. */
    public int peek() {
        if (out.isEmpty()) {
            while (!in.isEmpty()) {
                out.push(in.pop());
            }
        }
        return out.peek();
    }

    /** * Returns whether the queue is empty. */
    public boolean empty() {
        return in.isEmpty() && out.isEmpty();
    }
}

用队列实现栈


思路:维护两个队列,保证总有一个队列是空的

  • push操作,加入到非空的队列中
  • pop操作,将队列中size-1的数加入到空的队列,留下最后一个pop出去
  • top操作,将队列中size-1的数加入到空的队列,留下最后一个记录为top,再加入到新队列,返回top
  • empty操作,两个队列同时满足为空
class MyStack {

    LinkedList<Integer> queue1;
    LinkedList<Integer> queue2;

    /** * Initialize your data structure here. */
    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    /** * Push element x onto stack. */
    public void push(int x) {
        if (queue1.isEmpty()) {
            queue2.offer(x);
        } else {
            queue1.offer(x);
        }
    }

    /** * Removes the element on top of the stack and returns that element. */
    public int pop() {
        if (queue1.isEmpty()) {
            while (queue2.size() > 1) {
                queue1.offer(queue2.poll());
            }
            return queue2.poll();
        } else {
            while (queue1.size() > 1) {
                queue2.offer(queue1.poll());
            }
            return queue1.poll();
        }
    }

    /** * Get the top element. */
    public int top() {
        int top = 0;
        if (queue1.isEmpty()) {
            while (queue2.size() > 1) {
                queue1.offer(queue2.poll());
            }
            top = queue2.poll();
            queue1.offer(top);
        } else {
            while (queue1.size() > 1) {
                queue2.offer(queue1.poll());
            }
            top = queue1.poll();
            queue2.offer(top);
        }
        return top;
    }

    /** * Returns whether the stack is empty. */
    public boolean empty() {
        return queue2.isEmpty() && queue1.isEmpty();
    }
}

柱形图中的最大面积

解法一:暴力枚举高度

外层循环枚举每个节点
内层循环枚举从当前节点开始的后面每个节点,每当枚举一个节点就计算一次最低高度和最大面积

class Solution {
    public int largestRectangleArea(int[] heights) {
        int maxarea = 0;
        for (int i = 0; i < heights.length; i++) {
            int minheight = Integer.MAX_VALUE;
            for (int j = i; j < heights.length; j++) {
                minheight = Math.min(minheight,heights[j]);
                maxarea = Math.max(maxarea,minheight*(j-i+1));
            }
        }
        return maxarea;

    }
}

解法二:单调栈

官方题解,玩法太高端了,常看看

public class Solution {

    public int largestRectangleArea(int[] heights) {

        int len = heights.length;
        
        if (len == 0) return 0;
        if (len == 1) return heights[0];
        
        int maxSize = 0;
        
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);

        for (int i = 0; i < len; i++) {
            while (stack.peek() != -1 && heights[stack.peek()] >= heights[i]) {
                maxSize = Math.max(maxSize, heights[stack.pop()] * (i - stack.peek() - 1));
            }
            stack.push(i);
        }
        while (stack.peek() != -1) {
            maxSize = Math.max(maxSize, heights[stack.pop()] * (heights.length - stack.peek() - 1));
        }
        
        return maxSize;
    }
}

接雨水


压栈出栈
总体的原则就是:

  • 当前高度小于等于栈顶高度,入栈,指针后移。

  • 当前高度大于栈顶高度,出栈,计算出当前墙和栈顶的墙之间水的多少,然后计算当前的高度和新栈的高度的关系,重复第 2 步。直到当前墙的高度不大于栈顶高度或者栈空,然后把当前墙入栈,指针后移。

很好的题解

public class Solution {

    public int trap(int[] height) {
        int sum = 0;

        Stack<Integer> stack = new Stack<>();
        int current = 0;

        while (current < height.length) {
            //如果栈不为空且当前指向的高度大于栈顶高度就一直循环
            while (!stack.empty() && height[current] > height[stack.peek()]) {
                int h = height[stack.pop()];//要出栈的元素

                if (stack.isEmpty()) {//为空就存不了水
                    break;
                }
                int distance = current - stack.peek() - 1;//两堵墙之间的距离
                int min = Math.min(height[stack.peek()], height[current]);
                sum += distance * (min - h);
            }
            stack.push(current);//当前墙入栈
            current++;//指针后移

        }
        return sum;
    }
}

每日温度


运用栈,如果小于栈顶值存入栈,如果大于栈顶的值就将栈顶元素出栈,然后计算距离存入结果数组,反复出栈直到不满足大于栈顶元素

public class Solution {
    public int[] dailyTemperatures(int[] T) {
        Stack<Integer> stack = new Stack<>();
        int[] res = new int[T.length];

        for (int i = 0; i < T.length; i++) {
            while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
                Integer pre = stack.pop();
                res[pre] = i-pre;
            }
            stack.push(i);
        }
        return res;
    }
}

下一个更大元素II

和每日温度类似,只是循环链表用两倍数组长度求模来模拟了

public class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int len = nums.length;
        int[] res = new int[len];

        Arrays.fill(res, -1);

        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < 2 * len; i++) {
            while (!stack.isEmpty() && nums[i % len] > nums[stack.peek() % len]) {
                Integer pre = stack.pop();
                res[pre % len] = nums[i % len];
            }
            stack.push(i);
        }
        return res;
    }
}