《算法练习-文章汇总》

栈:先进后出

stack:添加和删除为O(1),查询为O(n)

队列:先进先出

queue:添加和删除为O(1),查询为O(n)

示例代码-Stack

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
System.out.println(stack);
System.out.println(stack.search(4));

stack.pop();
stack.pop();
Integer topElement = stack.peek();
System.out.println(topElement);
System.out.println("3的位置"+stack.search(3));

示例代码-Queue

Queue<String> queue = new LinkedList<String>();
queue.offer("one");
queue.offer("two");
queue.offer("three");
queue.offer("four");
System.out.println(queue);

String polledElement = queue.poll();
System.out.println(polledElement);
System.out.println(queue);

String peekedElement = queue.peek();
System.out.println(peekedElememt);
System.out.println(queue);

while(queue.size()>0){
   System.out.println(queue.poll());
}

示例代码-Deque

Deque<String> deque = new LinkedList<String>();
deque.push("a");
deque.push("b");
deque.push("c");
System.out.println(deque);

String str = deque.peek();
System.out.println(str);
System.out.println(deque);

while(deque.size()>0){
   System.out.println(deque.pop());
}

System.out.println(deque);

Priority Queue

• 1.插入操作:O(1);
• 2.取出操作:O(logN)-按照元素的优先级取出
• 3.底层具体实现的数据结构较为多样和复杂:heap

Java源码分析:
Stack:http://develop.classpath.org/doc/java/util/Stack-source.html
Queue:http://fuseyism.com/classpath/doc/java/util/Queue-source.html

作业:分析Queue和Priority Queue的源码

柱状图中最大矩形

https://leetcode-cn.com/problems/largest-rectangle-in-histogram/

1.暴力法

class Solution {
    public int largestRectangleArea(int[] heights) {
        int length = heights.length;
        int maxArea = 0;
        for(int left = 0;left < length;left++){
            int minHeight = Integer.MAX_VALUE;
            for(int right = left;right < length;right++){ 
                minHeight = Math.min(minHeight,heights[right]);
                maxArea = Math.max(maxArea,minHeight * (right - left + 1));
            }
        }
        return maxArea;
    }
}

2.栈

维护一个栈，一开始，把-1放进栈的顶部来表示开始。初始化时，按照从左到右的顺序，不断将柱子的需要放进栈中，知道遇到相邻柱子呈下降关系，也就是a[i-1]>a[i]。现在我们开始将栈中的序号弹出，知道遇到stack[j]满足a[stack[j]]<= a[i]。每次我们弹出下标时，我们用弹出元素作为高形成的最大面积矩形的宽是当前元素与stack[top - 1]之间的那些柱子。也就是当我们淡出stack[top]时，记当前元素在原数组中的下标为i,当前弹出元素为高的最大矩形面积为:
(i - stack[top - 1] - 1) * a[stack[top]]

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

3.单调栈

以上暴力写法 Java 可以通过，但我们不妨想一下这里的双重循环是否可以优化？

我们每遍历到当前柱体 i 时：

上述写法中，我们需要再嵌套一层 while 循环来向左找到第一个比柱体 i 高度小的柱体，这个过程是 O(N)O(N) 的；
那么我们可以 O(1)O(1) 的获取柱体 i 左边第一个比它小的柱体吗？答案就是单调增栈，因为对于栈中的柱体来说，栈中下一个柱体就是左边第一个高度小于自身的柱体。
因此做法就很简单了，我们遍历每个柱体，若当前的柱体高度大于等于栈顶柱体的高度，就直接将当前柱体入栈，否则若当前的柱体高度小于栈顶柱体的高度，说明当前栈顶柱体找到了右边的第一个小于自身的柱体，那么就可以将栈顶柱体出栈来计算以其为高的矩形的面积了。

class Solution {
    public int largestRectangleArea(int[] heights) {
        // 这里为了代码简便，在柱体数组的头和尾加了两个高度为 0 的柱体。
        int[] tmp = new int[heights.length + 2];
        System.arraycopy(heights, 0, tmp, 1, heights.length); 
        
        Deque<Integer> stack = new ArrayDeque<>();
        int area = 0;
        for (int i = 0; i < tmp.length; i++) {
            // 对栈中柱体来说，栈中的下一个柱体就是其「左边第一个小于自身的柱体」；
            // 若当前柱体 i 的高度小于栈顶柱体的高度，说明 i 是栈顶柱体的「右边第一个小于栈顶柱体的柱体」。
            // 因此以栈顶柱体为高的矩形的左右宽度边界就确定了，可以计算面积🌶️ ～
            while (!stack.isEmpty() && tmp[i] < tmp[stack.peek()]) {
                int h = tmp[stack.pop()];
                area = Math.max(area, (i - stack.peek() - 1) * h);   
            }
            stack.push(i);
        }

        return area;
    }
}

滑动窗口最大值

https://leetcode-cn.com/problems/sliding-window-maximum/

1.暴力法

最简单直接的方法是遍历每个滑动窗口，找到每个窗口的最大值。一共有 N - k + 1 个滑动窗口，每个有 k 个元素，于是算法的时间复杂度为 {O}(N k)O(Nk)，表现较差。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        if (n * k == 0) return new int[0];
        
        int [] output = new int[n - k + 1];
        for (int i = 0; i < n - k + 1; i++) {
            int max = Integer.MIN_VALUE;
            for(int j = i; j < i + k; j++) 
                max = Math.max(max, nums[j]);
            output[i] = max;
        }
        return output;
    }
}
复杂度分析

时间复杂度：{O}(N k)O(Nk)。其中 N 为数组中元素个数。

空间复杂度：{O}(N - k + 1)O(N−k+1)，用于输出数组。

2.双端队列

class Queue {
    void push(int n);
    // 或 enqueue，在队尾加入元素 n
    void pop();
    // 或 dequeue，删除队头元素
}
class MonotonicQueue {
    // 在队尾添加元素 n
    void push(int n);
    // 返回当前队列中的最大值
    int max();
    // 队头元素如果是 n，删除它
    void pop(int n);
}
class deque {
    // 在队头插入元素 n
    void push_front(int n);
    // 在队尾插入元素 n
    void push_back(int n);
    // 在队头删除元素
    void pop_front();
    // 在队尾删除元素
    void pop_back();
    // 返回队头元素
    int front();
    // 返回队尾元素
    int back();
}

public int[] maxSlidingWindow(int[] a, int k) {     
        if (a == null || k <= 0) {
            return new int[0];
        }
        int n = a.length;
        int[] r = new int[n-k+1];
        int ri = 0;
        // store index
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < a.length; i++) {
            // remove numbers out of range k
            while (!q.isEmpty() && q.peek() < i - k + 1) {
                q.poll();
            }
            // remove smaller numbers in k range as they are useless
            while (!q.isEmpty() && a[q.peekLast()] < a[i]) {
                q.pollLast();
            }
            // q contains index... r contains content
            q.offer(i);
            if (i >= k - 1) {
                r[ri++] = a[q.peek()];
            }
        }
        return r;
    }

预习题目

有效的括号
https://leetcode-cn.com/problems/valid-parentheses/

    //有效的括号
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (Character c:s.toCharArray()){
            if (c == '(') stack.push(')');
            else if(c == '[') stack.push(']');
            else if(c == '{') stack.push('}');
            else if(stack.isEmpty()|| stack.pop() != c) return false;
        }
        return stack.isEmpty();
    }

最小栈
https://leetcode-cn.com/problems/min-stack/

class MinStack {

    Stack<Integer>  stack;
    Stack<Integer>  minStack;
    public MinStack(){
        stack = new Stack<>();
        minStack = new Stack<>();
    }
    public void push(int n){
        stack.push(n);
        if(minStack.isEmpty() || n <= minStack.peek())
        minStack.push(n);
    }
    public void pop(){
            if(stack.pop().equals(minStack.peek()))
            minStack.pop();
    }
    public int top(){
        return stack.peek();
    }
    
    public int getMin(){
        return minStack.peek();
    }
}

课后作业

设计循环双端队列
https://leetcode-cn.com/problems/design-circular-deque/

设计实现双端队列。
你的实现需要支持以下操作：

MyCircularDeque(k)：构造函数,双端队列的大小为k。
insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true。
insertLast()：将一个元素添加到双端队列尾部。如果操作成功返回 true。
deleteFront()：从双端队列头部删除一个元素。 如果操作成功返回 true。
deleteLast()：从双端队列尾部删除一个元素。如果操作成功返回 true。
getFront()：从双端队列头部获得一个元素。如果双端队列为空，返回 -1。
getRear()：获得双端队列的最后一个元素。 如果双端队列为空，返回 -1。
isEmpty()：检查双端队列是否为空。
isFull()：检查双端队列是否满了。
示例：

MyCircularDeque circularDeque = new MycircularDeque(3); // 设置容量大小为3
circularDeque.insertLast(1);                    // 返回 true
circularDeque.insertLast(2);                    // 返回 true
circularDeque.insertFront(3);                   // 返回 true
circularDeque.insertFront(4);                   // 已经满了，返回 false
circularDeque.getRear();                // 返回 2
circularDeque.isFull();                     // 返回 true
circularDeque.deleteLast();                 // 返回 true
circularDeque.insertFront(4);                   // 返回 true
circularDeque.getFront();               // 返回 4

提示：
所有值的范围为 [1, 1000]
操作次数的范围为 [1, 1000]
请不要使用内置的双端队列库

public class MyCircularDeque {
    // 1、不用设计成动态数组，使用静态数组即可
    // 2、设计 head 和 tail 指针变量
    // 3、head == tail 成立的时候表示队列为空
    // 4、tail + 1 == head
    private int capacity;
    private int[] arr;
    private int front;
    private int rear;

    public MyCircularDeque(int k){
        capacity = k + 1;
        arr = new int[capacity];
        // 头部指向第 1 个存放元素的位置
        // 插入时，先减，再赋值
        // 删除时，索引 +1（注意取模）
        front = 0;
        // 尾部指向下一个插入元素的位置
        // 插入时，先赋值，再加
        // 删除时，索引 -1（注意取模）
        rear = 0;
    }

    public boolean insertFront(int value){
        if (isFull()){
            return false;
        }
        front = (front -1 + capacity)%capacity;
        arr[front] = value;
        return true;
    }

    public boolean insertLast(int value){
        if(isFull()){
            return false;
        }
        arr[rear] = value;
        rear = (rear + 1)% capacity;
        return true;
    }

    public boolean deleteFront(){
        if (isEmpty())
        return false;
        // front 被设计在数组的开头，所以是 +1
        front = (front + 1) % capacity;
        return true;
    }

    public boolean deleteLast(){
        if (isEmpty()) return  false;
        // rear 被设计在数组的末尾，所以是 -1
        rear = (rear - 1 + capacity) % capacity;
        return true;
    }

    public int getFront(){
        if (isEmpty()) return  -1;
        return arr[front];
    }

    public int getRear(){
        if (isEmpty()) return -1;
        // 当 rear 为 0 时防止数组越界
        return arr[(rear -1 + capacity) % capacity];
    }

    public boolean isEmpty(){
        return front == rear;
    }

    public boolean isFull(){
        // 注意：这个设计是非常经典的做法
         return (rear+1) %capacity == front;
    }
}

接雨水
https://leetcode-cn.com/problems/trapping-rain-water/

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

接雨水.png

方法一:暴力法

直观想法

直接按问题描述进行。对于数组中的每个元素，我们找出下雨后水能达到的最高位置，等于两边最大高度的较小值减去当前高度的值。
算法

初始化 ans=0ans=0
从左向右扫描数组：

初始化 \text{max_left}=0max_left=0 和 \text{max_right}=0max_right=0

从当前元素向左扫描并更新：
\text{max_left}=\max(\text{max_left},\text{height}[j])max_left=max(max_left,height[j])

从当前元素向右扫描并更新：
\text{max_right}=\max(\text{max_right},\text{height}[j])max_right=max(max_right,height[j])

将\min(\text{max_left},\text{max_right}) - \text{height}[i]min(max_left,max_right)−height[i] 累加到 \text{ans}ans

    public int requireRain(int[] nums) {
        int ans = 0;
        for (int i = 0; i < nums.length; i++) {
            int max_left = 0, max_right = 0;
            for (int j = i ; j >= 0; j--) {
                max_left = Math.max(max_left, nums[j]);
            }
            for (int k = i; k < nums.length; k++) {
                max_right = Math.max(nums[k], max_right);
            }
            ans += (Math.min(max_left, max_right) - nums[i]);
        }
        return ans;
    }

方法二:栈

直观想法

我们可以不用像方法 2 那样存储最大高度，而是用栈来跟踪可能储水的最长的条形块。使用栈就可以在一次遍历内完成计算。

我们在遍历数组时维护一个栈。如果当前的条形块小于或等于栈顶的条形块，我们将条形块的索引入栈，意思是当前的条形块被栈中的前一个条形块界定。如果我们发现一个条形块长于栈顶，我们可以确定栈顶的条形块被当前条形块和栈的前一个条形块界定，因此我们可以弹出栈顶元素并且累加答案到 \text{ans}ans 。

算法

使用栈来存储条形块的索引下标。
遍历数组：
当栈非空且 \text{height}[current]>\text{height}[st.top()]height[current]>height[st.top()]
意味着栈中元素可以被弹出。弹出栈顶元素 \text{top}top。
计算当前元素和栈顶元素的距离，准备进行填充操作
\text{distance} = \text{current} - \text{st.top}() - 1distance=current−st.top()−1

找出界定高度

\text{bounded_height} = \min(\text{height[current]}, \text{height[st.top()]}) - \text{height[top]}bounded_height=min(height[current],height[st.top()])−height[top]
往答案中累加积水量\text{ans} \mathrel{+}= \text{distance} \times \text{bounded_height}ans+=distance×bounded_height
将当前索引下标入栈
将 \text{current}current 移动到下个位置

    public int requireRain0(int[] nums) {
        int ans = 0;
        int currentIndex = 0;
        Stack<Integer> stack = new Stack<>();
        while (currentIndex < nums.length){
            while (!stack.isEmpty() && nums[currentIndex] > nums[stack.peek()]){
               int top = stack.peek();
               stack.pop();
               if (stack.isEmpty())
                   break;
               int distance = currentIndex - stack.peek() - 1;
               int boundHight = Math.min(nums[currentIndex],nums[stack.peek()])-nums[top];
               ans += distance*boundHight;
            }
            stack.push(currentIndex++);
        }
        return ans;
    }

方法三:双指针

直观想法
想办法一次完成遍历。
我们注意到，只要 \text{right_max}[i]>\text{left_max}[i]right_max[i]>left_max[i] （元素 0 到元素 6），积水高度将由 left_max 决定，类似地 \text{left_max}[i]>\text{right_max}[i]left_max[i]>right_max[i]（元素 8 到元素 11）。
所以我们可以认为如果一端有更高的条形块（例如右端），积水的高度依赖于当前方向的高度（从左到右）。当我们发现另一侧（右侧）的条形块高度不是最高的，我们则开始从相反的方向遍历（从右到左）。
我们必须在遍历时维护 \text{left_max}left_max 和 \text{right_max}right_max ，但是我们现在可以使用两个指针交替进行，实现 1 次遍历即可完成。

算法
初始化 \text{left}left 指针为 0 并且 \text{right}right 指针为 size-1
While \text{left}< \text{right}left<right, do:
If \text{height[left]}height[left] < \text{height[right]}height[right]
If \text{height[left]} \geq \text{left_max}height[left]≥left_max, 更新 \text{left_max}left_max
Else 累加 \text{left_max}-\text{height[left]}left_max−height[left] 到 \text{ans}ans
\text{left}left = \text{left}left + 1.
Else
If \text{height[right]} \geq \text{right_max}height[right]≥right_max, 更新 \text{right_max}right_max
Else 累加 \text{right_max}-\text{height[right]}right_max−height[right] 到 \text{ans}ans
\text{right}right = \text{right}right - 1.

C++

int Solution::trap(std::vector<int>& height)
{
    int left = 0,right = height.size()-1;
    int left_max = 0,right_max = 0;
    int ans = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            height[left] >= left_max ? left_max = height[left]: ans += (left_max-height[left]);
            left++;
        }else{
            height[right] >= right_max ? right_max = height[right] : ans += (right_max - height[right]);
            right--;
        }
    }
    return ans;
}

Java

    public int trap(int[] height){
        int left = 0,right = height.length - 1;
        int left_max = 0,right_max = 0;
        int ans = 0;
        while (left < right){
            if (height[left] < height[right]){
                if(height[left] >= left_max){
                    left_max = height[left];
                } else {
                    ans += (left_max - height[left]);
                }
                left++;
            }else {
                if (height[right] >= right_max){
                    right_max = height[right];
                }else{
                    ans += (right_max - height[right]);
                }
                right--;
            }
        }
        return ans;
    }