1. 栈与队列


  • 栈:先入后出。添加、删除皆为O(1),查询为O(n)
  • 队列:先入先出。添加、删除皆为O(1),查询为O(n)
  • 双端队列 Deque:Double-End Queue:添加、删除皆为O(1),查询为O(n)
  • 优先队列:根据优先级进行排序。插入O(1),取出O(logN)。底层数据结构比较复杂,heap、bst、treap

1.1.1. 用 add first 或 add last 这套新的 API 改写 Deque 的代码

1.1.2. 分析 Queue 和 Priority Queue 的源码

1.2. 剑指Offer 面试题

1.3. LeetCode 面试题

1.3.1. 20. 有效的括号

使用栈,一次遍历。

public boolean isValid(String s) {
    // 1. 建立Map,保存对应数据
    Map<Character, Character> map = new HashMap<>();
    map.put('(', ')');
    map.put('{', '}');
    map.put('[', ']');
    // 2. 建立栈
    Stack<Character> stack = new Stack<>();
    stack.push('?');
    // 3. 遍历字符串
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (!stack.peek().equals(c)){
            // 如果栈中不存在该符号,则将它的右半边括号加上
            if (map.containsKey(c)){
                stack.push(map.get(c));
            }else {
                // 如果本身就是右半边,直接输出错误
                return false;
            }
        }else{
            // 如果存在,则将它去了
            stack.pop();
        }
    }
    return stack.pop().equals('?');
}

1.3.2. 42. 接雨水

public int trap(int[] height) {
    ArrayDeque<Integer> deque = new ArrayDeque();
    int result = calc(height, deque);
    // 如果还剩下队列的时候,将首位减一
    while (deque.size() > 1) {
        deque.addFirst(deque.removeFirst()-1);
        height = new int[deque.size()];
        for (int i = 0; i < height.length; i++) {
            height[i] = deque.removeFirst();
        }
        result += calc(height, deque);
    }
    return result;
}

public int calc(int[] height, ArrayDeque<Integer> deque) {
    int result = 0;
    for (int value : height) {
        deque.addLast(value);
        if (deque.getFirst() == 0) { // 去除掉首个为0的
            deque.removeFirst();
        } else if (deque.getFirst() <= value) {//当右边大于左边时,计算值
            int min = deque.removeFirst();
            result += deque.stream().mapToInt(item -> Math.max(min - item, 0)).sum();
            deque.clear();
            deque.addFirst(value);
        }
    }
    return result;
}

1.3.3. 84. 柱状图中最大的矩形

暴力,O(n^2)

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;
}

1.3.4. 155. 最小栈

更新最小值时插入次小值,当删除的时候,通过两次pop取出次小值。

class MinStack {
    int min = Integer.MAX_VALUE;
    Stack<Integer> stack = new Stack<Integer>();
    public void push(int x) {
        // 当x小于最小值的时候,将最小值放入。
        if(x <= min){
            stack.push(min);
            min=x;
        }
        // 再插入原始值
        stack.push(x);
    }

    public void pop() {
        int res = stack.pop();
        // 当删除的值为最小值时,则取出次小值,否则最小值不变。
        if(res == min) {
            min=stack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return min;
    }
}

1.3.5. 225. 用队列实现栈

class MyStack {
    private Queue<Integer> queue;

    public MyStack() {
        queue = new LinkedList<>();
    }

    public void push(int x) {
        queue.add(x);
        // 如果大于1 ,则将前面添加的所有数,重新添加一次
        int lenth = queue.size();
        while (lenth > 1) {
            queue.add(queue.remove());
            lenth--;
        }
    }

    public int pop() {
        return queue.remove();
    }

    public int top() {
        return queue.peek();
    }

    public boolean empty() {
        return queue.isEmpty();
    }
}

1.3.6. 232. 用栈实现队列

一个用于入,一个用于出。只有当出的时候为空的时候,才往里面假数据,否则会把前面的数据压住。

class MyQueue {
    private Stack<Integer> stack;// 用于入
    private Stack<Integer> stack1;// 用于出

    public MyQueue() {
        stack = new Stack();
        stack1 = new Stack();
    }

    public void push(int x) {
        stack.push(x);
    }

    //只有当出的时候为空的时候,才往里面假数据,否则会把前面的数据压住。
    public void shift(){
        if (stack1.isEmpty()) {
            while (!stack.isEmpty()) {
                stack1.push(stack.pop());
            }
        }
    }

    public int pop() {
        shift();
        return stack1.pop();
    }


    public int peek() {
        shift();
        return stack1.peek();
    }

    public boolean empty() {
        return stack1.isEmpty() && stack.isEmpty();

    }
}

1.3.7. 239. 滑动窗口最大值

使用一个队列,保持k的大小,不断移动。每次等于k时,求一次最大值。

public int[] maxSlidingWindow(int[] nums, int k) {
    if (nums.length==0){
        return new int[0];
    }
    int[] result = new int[nums.length - k + 1];
    ArrayList<Integer> list = new ArrayList(nums.length - k + 1);
    Queue<Integer> queue = new LinkedList<>();
    for (int num : nums) {
        // 如果等于k时候,计算最大值,然后移动
        if (queue.size() >= k) {
            list.add(Collections.max(queue));
            queue.remove();
        }
        queue.add(num);
    }
    // 为最后一个添加的数据求最大值
    list.add(Collections.max(queue));
    for (int i = 0; i < list.size(); i++) {
        result[i] = list.get(i);
    }
    return result;
}

1.3.8. 503. 下一个更大元素 II

暴力

public int[] nextGreaterElements(int[] nums) {
    if (nums.length == 0) {
        return new int[0];
    }
    // 1. 返回数据,将它填-1
    int[] ans = new int[nums.length];
    Arrays.fill(ans, -1);
    // 2. 将循环拉平[1,2,3]>>[1,2,3,1,2]
    int[] doubleNums = new int[nums.length * 2 - 1];
    System.arraycopy(nums, 0, doubleNums, 0, nums.length);
    System.arraycopy(nums, 0, doubleNums, nums.length, nums.length - 1);
    // 3. 遍历,找到需要的结果
    for (int i = 0; i < nums.length; i++) {
        for (int j = 1; j < nums.length; j++) {
            if (nums[i] < doubleNums[j + i]) {
                ans[i] = doubleNums[j + i];
                break;
            }
        }
    }
    return ans;
}

单调栈,看不太懂。视频教程

public int[] nextGreaterElements(int[] nums) {
    int [] ans = new int[nums.length];
    Arrays.fill(ans,-1);
    int [] doubleNums = new int[2*nums.length];
    System.arraycopy(nums,0,doubleNums,0,nums.length);
    System.arraycopy(nums,0,doubleNums,nums.length,nums.length);
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < doubleNums.length; i++) {
        while (!stack.isEmpty()&&doubleNums[stack.peek()]<doubleNums[i]){
            if (stack.peek()<nums.length){
                ans[stack.pop()] = doubleNums[i];
            }else{
                stack.add(i);
            }
        }
        stack.add(i);
    }
    return ans;
}

1.3.9. 739. 每日温度

暴力

public int[] dailyTemperatures(int[] T) {
    // 1. 返回结果
    int[] ans = new int[T.length];
    // 2. 暴力求解
    for (int i = 0; i < T.length; i++) {
        for (int j = i; j < T.length; j++) {
            if (T[i] < T[j]) {
                ans[i] = j - i;
                break;
            }
        }
    }
    return ans;
}

使用栈。看了这个视频

public int[] dailyTemperatures(int[] T) {
    int[] ans = new int[T.length];
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < T.length; i++) {
        while (!stack.isEmpty()) {
            if (T[i] > T[stack.peek()]) {
                int temp = stack.pop();
                ans[temp] = i - temp;
            }else{
                break;
            }
        }
        stack.add(i);
    }
    return ans;
}

results matching ""

    No results matching ""