Java教程

算法:栈相关经典算法题目

本文主要是介绍算法:栈相关经典算法题目,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

栈相关题目

文章目录

  • 栈相关题目
    • 一、[20. 有效的括号](https://leetcode-cn.com/problems/valid-parentheses/)
      • 1.1 解法一: 使用Stack栈(FILO)来实现(可以使用双端队列代替)
    • 二、[155. 最小栈](https://leetcode-cn.com/problems/min-stack/)
      • 2.1 解法一:自定义栈
      • 2.2 解法二:使用辅助栈
    • 三、[84. 柱状图中最大的矩形](https://leetcode-cn.com/problems/largest-rectangle-in-histogram/) , 经常回过来看看
      • 3.1 解法一:暴力求解,时间超限
      • 3.2 解法二:暴力求解的优化,(以当前角标值作为高度),时间超限
      • 3.3 解法三:用栈来解决
        • (1) 根据这个思路,自己写:
        • (2) 对代码进行优化
    • 四、[239. 滑动窗口最大值](https://leetcode-cn.com/problems/sliding-window-maximum/)
      • 4.1 解法一:维护一个递减队列
    • 五、[641. 设计循环双端队列](https://leetcode-cn.com/problems/design-circular-deque/)
    • 六、[42. 接雨水](https://leetcode-cn.com/problems/trapping-rain-water/)
      • 6.1 解法一:使用栈来解决

一、20. 有效的括号

1.1 解法一: 使用Stack栈(FILO)来实现(可以使用双端队列代替)

    public boolean isValid(String s) {
        Deque<Character> deque = new LinkedList<>();
        Map<Character, Character> map = new HashMap<>(3);
        map.put(')', '(');
        map.put('}', '{');
        map.put(']', '[');
        for (int i=0; i<s.length(); i++) {
            char c = s.charAt(i);
            if (!map.containsKey(c)) {
                deque.addFirst(c);
            }else {
                if (deque.isEmpty() || deque.peek()!=map.get(c)) return false;
                deque.removeFirst();
            }
        }
        return deque.isEmpty();
    }

二、155. 最小栈

2.1 解法一:自定义栈

栈:先进先出。最小栈:每个节点保留最小值;

class MinStack {

    private Node first;
    private int N;

    private class Node {
        private int val;
        private int min;
        private Node next;
        public Node(int val, int min) {
            this.val = val;
            this.min  = min;
        }

    }

    public MinStack() {
    }

    public int size() {
        return N;
    }

    public boolean isEmpty() {
        return size()==0;
    }
    
    public void push(int val) {
        if (isEmpty()) {
            first = new Node(val, val);
        }else {
            Node oldFirst = first;
            first = new Node(val, Math.min(val, first.min));
            first.next = oldFirst;
        }
        N++;
    }
    
    public void pop() {
        if (isEmpty()) return;
        first = first.next;
        N--;
    }
    
    public int top() {
        if (isEmpty()) throw new RuntimeException("None item");
        return first.val;
    }
    
    public int getMin() {
        if (isEmpty()) throw new RuntimeException("None item");
        return first.min;
    }
}

2.2 解法二:使用辅助栈

class MinStack {

    private Deque<Integer> stack;
    private Deque<Integer> minStack;

    public MinStack() {
        stack = new LinkedList<>();
        minStack = new LinkedList<>();
        minStack.push(Integer.MAX_VALUE);
    }
    
    public void push(int val) {
        stack.push(val);
        minStack.push(Math.min(val, minStack.peek()));
    }
    
    public void pop() {
        stack.pop();
        minStack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

三、84. 柱状图中最大的矩形 , 经常回过来看看

3.1 解法一:暴力求解,时间超限

    public int largestRectangleArea(int[] heights) {
        int max = 0;
        for (int i=0; i<heights.length; i++) {
            int minH = heights[i];
            for (int j=i; j<heights.length; j++) {
                minH = Math.min(heights[j], minH);
                int area = (j-i+1) * minH;
                max = Math.max(area, max);
            }
        }
        return max;
    }

3.2 解法二:暴力求解的优化,(以当前角标值作为高度),时间超限

    public int largestRectangleArea(int[] heights) {
        int max = 0;
        for (int k=0; k<heights.length; k++) {
            // 找左边界 和右边界
            int l = k-1, r = k+1;
            while (l>=0 && heights[l]>=heights[k]) l--;
            while (r<=heights.length-1 && heights[r]>=heights[k]) r++;
            int area = (r-l-1) * heights[k];
            max = Math.max(area, max);
        }
        return max;
    }

3.3 解法三:用栈来解决

基于“以当前角标对应的值作为高,再获取到左边界、和右边界,进来计算出面积”

维护一个递增的栈(栈里面存放角标),这样左边界就确定了。

因为是递增,如果进栈元素比栈顶的元素小,那边右边界就也能确定了。

(1) 根据这个思路,自己写:

    public int largestRectangleArea(int[] heights) {
        Deque<Integer> deque = new LinkedList<>();
        deque.addFirst(-1);
        int max=0;
        for (int i=0; i<=heights.length; i++) {
            if (i==heights.length || (deque.peek()!=-1 && heights[deque.peek()]>heights[i])){
                while ((i==heights.length && deque.peek()!=-1) || (deque.peek()!=-1 && heights[deque.peek()]>heights[i])) {
                    int h_i = deque.removeFirst();
                    while (deque.peek() != -1 && heights[deque.peek()] == heights[h_i]) h_i = deque.removeFirst();
                    int l_i = deque.peek();
                    int r_i = i;
                    int area = (r_i - l_i - 1) * heights[h_i];
                    max = Math.max(area, max);
                }
            }
            deque.addFirst(i);
        }
        return max;
    }

(2) 对代码进行优化

    public int largestRectangleArea(int[] heights) {
        Deque<Integer> deque = new LinkedList<>();
        deque.addFirst(-1);
        int max = 0;
        for (int i=0; i<heights.length; i++) {
            while (deque.peek()!=-1 && heights[deque.peek()]>heights[i]) {
                int area = heights[deque.removeFirst()] * (i-deque.peek()-1);
                max = Math.max(area, max);
            }
            deque.addFirst(i);
        }
        while (deque.peek()!=-1) {
            int area = heights[deque.removeFirst()] * (heights.length - deque.peek()-1);
            max = Math.max(area, max);
        }
        return max;
    }

四、239. 滑动窗口最大值

4.1 解法一:维护一个递减队列

    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] res = new int[nums.length-k+1];
        Deque<Integer> deque = new LinkedList<>();
        for (int i=0; i<nums.length; i++) {
            while (!deque.isEmpty() && nums[deque.peekLast()]<=nums[i]) {
                deque.removeLast();
            }
            deque.addLast(i);
            int j = i-k+1;
            if (deque.peekFirst()<j) {
                deque.removeFirst();
            }
            if (j>=0) {
                res[j] = nums[deque.peekFirst()];
            }
        }
        return res;
    }

五、641. 设计循环双端队列

class MyCircularDeque {

    private Node first, last;
    private int N;
    private int capacity;

    private class Node{
        private int value;
        private Node next,pre;
        public Node(int value) {
            this.value = value;
        }
    }

    public MyCircularDeque(int k) {
        this.capacity = k;
    }
    
    public boolean insertFront(int value) {
        if (isFull()) return false;
        Node node = new Node(value);
        if (isEmpty()) {
            first = node;
            last = node;
        }else {
            Node oldFirst = first;
            first = node;
            first.next = oldFirst;
            oldFirst.pre = first;
            first.pre = last;
            last.next = first;
        }
        N++;
        return true;
    }
    
    public boolean insertLast(int value) {
        if (isFull()) return false;
        Node node = new Node(value);
        if (isEmpty()) {
            last = node;
            first = last;
        }else {
            Node oldLast = last;
            last = node;
            last.next = first;
            last.pre = oldLast;
            first.pre = last;
            oldLast.next = last;
        }
        N++;
        return true;
    }
    
    public boolean deleteFront() {
        if (isEmpty()) return false;
        if (size()==1) {
            first=null;
            last =null;
        }else {
            Node oldFirst = first;
            first = oldFirst.next;
            first.pre = last;
            last.next = first;
        }
        N--;
        return true;
    }
    
    public boolean deleteLast() {
        if (isEmpty()) return false;
        if (size()==1) {
            first = null;
            last = null;
        }else {
            Node oldLast = last;
            last = oldLast.pre;
            last.next = first;
            first.pre = last;
        }
        N--;
        return true;
    }
    
    public int getFront() {
        if (isEmpty()) return -1;
        return first.value;
    }
    
    public int getRear() {
        if (isEmpty()) return -1;
        return last.value;
    }

    public int size() {
        return N;
    }
    
    public boolean isEmpty() {
        return size() == 0;
    }
    
    public boolean isFull() {
        return size()==capacity;
    }
}

六、42. 接雨水

6.1 解法一:使用栈来解决

    public int trap(int[] height) {
        if (height==null || height.length<3) return 0;
        Deque<Integer> deque = new LinkedList<>();
        int container = 0;
        for (int i=0; i<height.length; i++) {
            while (!deque.isEmpty() && height[i]>height[deque.peek()]) {
                int lo = deque.removeFirst();
                if (deque.isEmpty()) break;
                int left = deque.peek();
                int width = i - left - 1;
                int high = Math.min(height[i], height[left])-height[lo];
                container += width * high;
            }
            deque.addFirst(i);
        }
        return container;
    }
这篇关于算法:栈相关经典算法题目的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!