• 算法和数据结构解析-8 : 栈和队列相关问题

    1. 栈和队列数据结构

    1.1 栈（Stack）

    栈（Stack）又名堆栈，它是一种重要的数据结构。从数据结构角度看，栈也是线性表，其特殊性在于栈的基本操作是线性表操作的子集，它是操作受限的线性表，因此，可称为限定性的数据结构。

    栈被限定仅在表尾进行插入或删除操作。表尾称为栈顶，相应地，表头称为栈底。所以栈具有“后进先出”（LIFO）的特点。

    栈的基本操作除了在栈顶进行插入（入栈，push）和删除（出栈，pop）外，还有栈的初始化，判断是否为空以及取栈顶元素等。

     1.2 队列

    队列（Queue）是一种先进先出（FIFO，First-In-First-Out）的线性表。

    在具体应用中通常用链表或者数组来实现。队列只允许在后端（称为 rear）进行插入操作，在前端（称为 front）进行删除操作。

    队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加。

    • 双端队列 (Deque:double ended queue)

    双端队列，是限定插入和删除操作在表的两端进行的线性表。

    队列的每一端都能够插入数据项和移除数据项。

    相对于普通队列，双端队列的入队和出队操作在两端都可进行。所以，双端队列同时具有队列和栈的性质。

    • 优先队列

    优先队列不再遵循先入先出的原则，而是分为两种情况：

    最大优先队列，无论入队顺序，当前最大的元素优先出队。

    最小优先队列，无论入队顺序，当前最小的元素优先出队。

    比如有一个最大优先队列，它的最大元素是8，那么虽然元素8并不是队首元素，但出队的时候仍然让元素8首先出队：

     

    要满足以上需求，利用线性数据结构并非不能实现，但是时间复杂度较高，需要遍历所有元素，最坏时间复杂度O（n），并不是最理想的方式。

    因此，一般是用大顶堆（Max Heap，有时也叫最大堆）来实现最大优先队列，每一次入队操作就是堆的插入操作，每一次出队操作就是删除堆顶节点。

    入队操作：

    1. 插入新节点5

    2. 新节点5上浮到合适位置。

     

    出队操作：

    1.把原堆顶节点10“出队”

    2.最后一个节点1替换到堆顶位置

    3.节点1下沉，节点9成为新堆顶

    二叉堆节点上浮和下沉，操作次数不会超过数的深度，所以时间复杂度都是O(logn)。那么优先队列，入队和出队的时间复杂度，也是O(logn)。

    2.使用队列实现栈

    2.1 题目说明

    使用队列实现栈的下列操作：

    • push(x) -- 元素 x 入栈
    • pop() -- 移除栈顶元素
    • top() -- 获取栈顶元素
    • empty() -- 返回栈是否为空

    注意:

    • 你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
    • 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
    • 你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

     2.2 分析

    这道题目涉及到栈和队列两种数据结构。它们的共同特点是，数据元素以线性序列的方式存储；区别在于，元素进出的方式不同。

    队列本身对数据元素的保存，是完全符合数据到来次序的，同时也保持这个顺序依次出队。而弹栈操作的实现，是要删除最后进入的数据，相当于反序弹出。

    实现的基本思路是，我们可以用一个队列保存当前所有的数据，以它作为栈的物理基础；而为了保证后进先出，我们在数据入队之后，就把它直接移动到队首。

    2.3 方法一：两个队列实现

    可以增加一个队列来做辅助。我们记原始负责存储数据的队列为queue1，新增的辅助队列为queue2。

    • 当一个数据x压栈时，我们不是直接让它进入queue1，而是先在queue2做一个缓存。默认queue2中本没有数据，所以当前元素一定在队首。

    queue1：a b

    queue2：x

    • 接下来，就让queue1执行出队操作，把之前的数据依次输出，同时全部添加到queue2中来。这样，queue2就实现了把新元素添加到队首的目的。

    queue1：

    queue2：x a b

    • 最后，我们将queue2的内容复制给queue1做存储，然后清空queue2。在代码上，这个实现非常简单，只要交换queue1和queue2指向的内容即可。

    queue1：x a b

    queue2：

    而对于弹栈操作，只要直接让queue1执行出队操作，删除队首元素就可以了。

    1. package com.webcode.stack_and_queue;
    2.  
    3. import java.util.LinkedList;
    4. import java.util.Queue;
    5. import java.util.Stack;
    6.  
    7. // 使用两个队列实现自定义栈
    8. public class MyStack {
    9.     // 定义两个队列
    10.     Queue queue1;
    11.     Queue queue2;
    12.  
    13.     public MyStack() {
    14.         queue1 = new LinkedList<>();
    15.         queue2 = new LinkedList<>();
    16.     }
    17.  
    18.     // 入栈方法
    19.     public void push(int x){
    20.         // 1. 把x保存到queue2中
    21.         queue2.offer(x);
    22.  
    23.         // 2. 将queue1中所有元素依次出队，然后放入queue2
    24.         while (!queue1.isEmpty()){
    25.             queue2.offer( queue1.poll() );
    26.         }
    27.  
    28.         // 3. 交换两个队列
    29.         Queue temp = queue1;
    30.         queue1 = queue2;
    31.         queue2 = temp;
    32.     }
    33.  
    34.     // 出栈操作
    35.     public int pop(){
    36.         // queue1出队就是出栈
    37.         return queue1.poll();
    38.     }
    39.  
    40.     // 获取栈顶元素
    41.     public int top(){
    42.         return queue1.peek();
    43.     }
    44.  
    45.     // 判断为空
    46.     public boolean empty(){
    47.         return queue1.isEmpty();
    48.     }
    49. }

    复杂度分析

    时间复杂度：入栈操作 O(n)，其余操作都是 O(1)。

    push：入栈操作，需要将queue1中的 n 个元素出队，并入队 n+1 个元素到 queue2，总计 2n+1 次操作。每次出队和入队操作的时间复杂度都是 O(1)，因此入栈操作的时间复杂度是 O(n)。

    pop：出栈操作，只是将queue1的队首元素出队，时间复杂度是 O(1)。

    top：获得栈顶元素，对应获得queue1的队首元素，时间复杂度是 O(1)。

    isEmpty：判断栈是否为空，只需要判断queue1是否为空，时间复杂度是 O(1)。

    空间复杂度：O(n)，其中 n 是栈内的元素。需要使用两个队列存储栈内的元素。

     2.4 方法二：一个队列实现

    当一个新的元素x压栈时，其实我们可以不借助辅助队列，而是让它直接入队queue1，它会添加在队尾。然后接下来，只要将之前的所有数据依次出队、再重新入队添加进queue1，就自然让x移动到队首了。

    1. // 用一个队列实现自定义栈
    2. public class MyStack2 {
    3.     // 定义一个队列
    4.     Queue queue;
    5.  
    6.     public MyStack2() {
    7.         queue = new LinkedList<>();
    8.     }
    9.  
    10.     public void push(int x){
    11.         // 1. 首先记录当前队列长度
    12.         int l = queue.size();
    13.  
    14.         // 2. 把x入队
    15.         queue.offer(x);
    16.  
    17.         // 3. 把queue中原先的所有元素依次出队，然后再入队
    18.         for (int i = 0; i < l; i++)
    19.             queue.offer( queue.poll() );
    20.     }
    21.  
    22.     public int pop(){
    23.         return queue.poll();
    24.     }
    25.  
    26.     public int top(){
    27.         return queue.peek();
    28.     }
    29.  
    30.     public boolean empty(){
    31.         return queue.isEmpty();
    32.     }
    33. }

     复杂度分析

    时间复杂度：入栈操作 O(n)，其余操作都是 O(1)。

    push：入栈操作，需要将queue1中的 n 个元素出队，并入队 n+1 个元素到 queue2，总计 2n+1 次操作。每次出队和入队操作的时间复杂度都是 O(1)，因此入栈操作的时间复杂度是 O(n)。

    pop：出栈操作。只是将queue1的队首元素出队，时间复杂度是 O(1)。

    top：获得栈顶元素，对应获得queue1的队首元素，时间复杂度是 O(1)。

    isEmpty：判断栈是否为空，只需要判断queue1是否为空，时间复杂度是 O(1)。

    空间复杂度：O(n)，其中 n 是栈内的元素。需要使用两个队列存储栈内的元素。

    3. 使用栈实现队列

    3.1 题目说明

    请你仅使用两个栈实现先入先出队列。队列应当支持一般队列的支持的所有操作（push、pop、peek、empty）：

    实现 MyQueue 类：

    1. void push(int x) 将元素 x 推到队列的末尾
    2. int pop() 从队列的开头移除并返回元素
    3. int peek() 返回队列开头的元素
    4. boolean empty() 如果队列为空，返回 true ；否则，返回 false 

    说明：

    1. 你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
    2. 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

    进阶：

    你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。

    示例：

    输入：
    ["MyQueue", "push", "push", "peek", "pop", "empty"]
    [[], [1], [2], [], [], []]
    输出：
    [null, null, null, 1, 1, false]

    解释：

    MyQueue myQueue = new MyQueue();

    myQueue.push(1); // queue is: [1]

    myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)

    myQueue.peek(); // return 1

    myQueue.pop(); // return 1, queue is [2]

    myQueue.empty(); // return false 

    提示：

    • 1 <= x <= 9
    • 最多调用 100 次 push、pop、peek 和 empty
    • 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）

    3.2 分析

    我们要用栈来实现队列。一个队列是 FIFO 的，但一个栈是 LIFO 的。为了满足队列的 FIFO 的特性，我们需要将入栈的元素次序进行反转，这样在出队时就可以按照入队顺序依次弹出了。

    想要反转，简单的想法是只要把所有元素依次弹出，并压入另一个栈，自然就变成本来栈底元素到了栈顶了。所以我们的实现，需要用到两个栈。 

    3.3 方法一：入队时反转

    一种直观的思路是，最终的栈里，按照“自顶向下”的顺序保持队列。也就是说，栈顶元素是最先入队的元素，而最新入队的元素要压入栈底。

    我们可以用一个栈来存储元素的最终顺序（队列顺序），记作stack1；用另一个进行辅助反转，记作stack2。

    最简单的实现，就是直接用stack2，来缓存原始压栈的元素。每次调用push，就把stack1中的元素先全部弹出并压入stack2，然后把新的元素也压入stack2；这样stack2就是完全按照原始顺序入栈的。最后再把stack2中的元素全部弹出并压入stack1，进行反转。

    1. package com.webcode.stack_and_queue;
    2.  
    3. import java.util.Stack;
    4.  
    5. // 用两个栈实现队列：入队时翻转
    6. public class MyQueue {
    7.     // 定义两个栈
    8.     Stack stack1;
    9.     Stack stack2;
    10.  
    11.     public MyQueue() {
    12.         stack1 = new Stack<>();
    13.         stack2 = new Stack<>();
    14.     }
    15.  
    16.     // 入队方法
    17.     public void push(int x){
    18.         // 1. 首先将stack1中所有元素弹出，压入stack2
    19.         while (!stack1.isEmpty())
    20.             stack2.push( stack1.pop() );
    21.  
    22.         // 2. 将新元素压入stack1
    23.         stack1.push(x);
    24.  
    25.         // 3. 再将stack2中所有元素弹出，压入stack
    26.         while (!stack2.isEmpty())
    27.             stack1.push( stack2.pop() );
    28.     }
    29.  
    30.     // 出队方法
    31.     public int pop(){
    32.         return stack1.pop();
    33.     }
    34.  
    35.     // 获取队首元素
    36.     public int peek(){
    37.         return stack1.peek();
    38.     }
    39.  
    40.     // 判空
    41.     public boolean empty(){
    42.         return stack1.isEmpty();
    43.     }
    44.  
    45.     public static void main(String[] args) {
    46.         MyQueue myQueue = new MyQueue();
    47.         myQueue.push(1); // queue is: [1]
    48.         myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
    49.         myQueue.peek(); // return 1
    50.         myQueue.pop(); // return 1, queue is [2]
    51.         myQueue.empty(); // return false
    52.     }
    53. }

     复杂度分析

    • 入队

    时间复杂度：O(n)

    除新元素之外，所有元素都会被压入两次，弹出两次。新元素被压入两次，弹出一次。（当然，我们可以稍作改进，在stack1清空之后把新元素直接压入，就只压入一次了）

    这个过程产生了4n+3 次操作，其中 n 是队列的大小。由于入栈操作和弹出操作的时间复杂度为 O(1)， 所以时间复杂度为 O(n)。

    空间复杂度：O(n)

    需要额外的内存来存储队列中的元素。

    • 其它操作（pop、peek、isEmpty）

    时间复杂度：O(1)

    空间复杂度：O(1)

    3.4 方法二：出队时反转

    可以不要在入队时反转，而是在出队时再做处理。

    执行出队操作时，我们想要弹出的是stack1的栈底元素。所以需要将stack1中所有元素弹出，并压入stack2，然后弹出stack2的栈顶元素。

    我们观察可以发现，stack2中的元素，其实就是保持着队列顺序的，所以完全没必要将它们再压回stack1，下次出队时，我们只要直接弹出stack2中的栈顶元素就可以了。

    1. package com.webcode.stack_and_queue;
    2.  
    3. import java.util.Stack;
    4.  
    5. // 用两个栈实现队列：入队时翻转
    6. public class MyQueue2 {
    7.     // 定义两个栈
    8.     Stack stack1;
    9.     Stack stack2;
    10.  
    11.     public MyQueue2() {
    12.         stack1 = new Stack<>();
    13.         stack2 = new Stack<>();
    14.     }
    15.  
    16.     // 入队方法
    17.     public void push(int x){
    18.         stack1.push(x);
    19.     }
    20.  
    21.     // 出队方法
    22.     public int pop(){
    23.         stack2 = new Stack<>();
    24.         while (!stack1.isEmpty()){
    25.             stack2.push(stack1.pop());
    26.         }
    27.         return stack2.pop();
    28.     }
    29.  
    30.     // 获取队首元素
    31.     public int peek(){
    32.         stack2 = new Stack<>();
    33.         while (!stack1.isEmpty()){
    34.             stack2.push(stack1.pop());
    35.         }
    36.         return stack1.peek();
    37.     }
    38.  
    39.     // 判空
    40.     public boolean empty(){
    41.         return stack1.isEmpty();
    42.     }
    43.  
    44.     public static void main(String[] args) {
    45.         MyQueue2 myQueue = new MyQueue2();
    46.         myQueue.push(1); // queue is: [1]
    47.         myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
    48.         myQueue.peek(); // return 1
    49.         myQueue.pop(); // return 1, queue is [2]
    50.         myQueue.empty(); // return false
    51.     }
    52. }

    复杂度分析

    • 入队（push）

    时间复杂度：O(1)。向栈压入元素的时间复杂度为O(1)

    空间复杂度：O(n)。需要额外的内存（stack1和stack2共同存储）来存储队列元素。

    • 出队（pop）

    时间复杂度： 摊还复杂度 O(1)，最坏情况下的时间复杂度 O(n)

    在最坏情况下，stack2 为空，算法需要执行while循环进行反转。具体过程是从 stack1 中弹出 n 个元素，然后再把这 n 个元素压入 stack2，在这里n代表队列的大小。这个过程产生了 2n 步操作，时间复杂度为 O(n)。

    但当 stack2 非空时，只需要直接弹栈，算法就只有 O(1) 的时间复杂度。均摊下来，摊还复杂度为O(1)。

    空间复杂度 ：O(1)

    • 取队首元素（peek）和判断是否为空（empty）

    时间复杂度：O(1)

    空间复杂度：O(1)

     3.5 摊还复杂度分析

    摊还分析（Amortized Analysis，均摊法），用来评价某个数据结构的一系列操作的平均代价。

    对于一连串操作而言，可能某种情况下某个操作的代价特别高，但总体上来看，也并非那么糟糕，可以形象的理解为把高代价的操作“分摊”到其他操作上去了，要求的就是均摊后的平均代价。

    摊还分析的核心在于，最坏情况下的操作一旦发生了一次，那么在未来很长一段时间都不会再次发生，这样就会均摊每次操作的代价。

    摊还分析与平均复杂度分析的区别在于，平均情况分析是平均所有的输入。而摊还分析是平均操作。在摊还分析中，不涉及概率，并且保证在最坏情况下每一个操作的平均性能。

    所以摊还分析，往往会用在某一数据结构的操作分析上。

    4. 有效的括号

    4.1 题目说明

    给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

    有效字符串需满足：

    1. 左括号必须用相同类型的右括号闭合。
    2. 左括号必须以正确的顺序闭合。

    注意空字符串可被认为是有效字符串。

    示例 1:

    输入: "()"

    输出: true

    示例 2:

    输入: "()[]{}"

    输出: true

    示例 3:

    输入: "(]"

    输出: false

    示例 4:

    输入: "([)]"

    输出: false

    示例 5:

    输入: "{[]}"

    输出: true

    4.2 分析

    判断括号的有效性，这是一个非常经典的问题。

    由于给定字符串中只包含 '('，')'，'{'，'}'，'['，']' ，所以我们不需要额外考虑非法字符的问题。

    对于合法的输入字符，关键在于遇到一个“左括号”时，我们会希望在后续的遍历中，遇到一个相同类型的“右括号”将其闭合。

    由于规则是：后遇到的左括号，要先闭合，因此我们想到，利用一个栈可以实现这个功能，将左括号放入栈顶，遇到右括号时弹出就可以了。

    4.3 具体实现

    代码实现非常简单：我们可以创建一个栈，然后遍历字符串。遇到左括号，就压栈；遇到右括号，就判断和当前栈顶的左括号是否匹配，匹配就弹栈，不匹配直接返回false。

    1. public class ValidParentheses {
    2.     // 使用栈
    3.     public boolean isValid(String s){
    4.         Deque stack = new LinkedList<>();
    5.  
    6.         // 遍历字符串中所有字符，依次判断
    7.         for (int i = 0; i < s.length(); i++){
    8.             // 获取当前字符
    9.             char ch = s.charAt(i);
    10.  
    11.             // 判断当前字符是左括号还是右括号
    12.             // 如果是左括号，直接将对应的右括号入栈
    13.             if ( ch == '(' ){
    14.                 stack.push(')');
    15.             } else if ( ch == '[' ){
    16.                 stack.push(']');
    17.             } else if ( ch == '{' ){
    18.                 stack.push('}');
    19.             } else {
    20.                 // 如果是右括号，弹栈判断是否匹配
    21.                 if (stack.isEmpty() || stack.pop() != ch) return false;
    22.             }
    23.         }
    24.  
    25.         return stack.isEmpty();
    26.     }
    27.  
    28.     public static void main(String[] args) {
    29.         ValidParentheses validParentheses = new ValidParentheses();
    30.  
    31.         System.out.println(validParentheses.isValid("()[]{}"));
    32.         System.out.println(validParentheses.isValid("(]"));
    33.         System.out.println(validParentheses.isValid("([)]"));
    34.         System.out.println(validParentheses.isValid("{[]}"));
    35.     }
    36. }

    复杂度分析

    时间复杂度：O(n)，其中n是字符串s的长度。只需要遍历一次字符串。

    空间复杂度：O(n)。栈中最多会保存字符串中所有的左括号，数量为O(n)。

    5.柱状图中最大的矩形

    5.1 题目说明

    给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

    求在该柱状图中，能够勾勒出来的矩形的最大面积。

    以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。 

    图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

    示例:

    输入: [2,1,5,6,2,3]

    输出: 10

     5.2 分析

    题目要求计算最大矩形面积，我们可以发现，关键其实就在于确定矩形的“宽”和“高”（即矩形面积计算中的长和宽）。

    而宽和高两者间又有制约条件：一定宽度范围内的高，就是最矮那个柱子的高度。

    5.3 方法一：暴力法

    一个简单的思路，就是遍历所有可能的宽度。也就是说，以每个柱子都作为矩形的左右边界进行计算，取出所有面接中最大的那个。

    1.     // 方法一：暴力法（遍历所有可能的宽度）
    2.     public int largestRectangleArea1(int[] heights){
    3.         // 定义变量保存最大面积
    4.         int largestArea = 0;
    5.  
    6.         // 遍历数组，作为矩形左边界
    7.         for (int left = 0; left < heights.length; left ++){
    8.             // 定义变量保存当前矩形高度
    9.             int currHeight = heights[left];
    10.  
    11.             // 遍历数组，选取矩形右边界
    12.             for (int right = left; right < heights.length; right ++){
    13.                 // 确定当前矩形的高度
    14.                 currHeight = (heights[right] < currHeight) ? heights[right] : currHeight;
    15.  
    16.                 // 计算当前矩形面积
    17.                 int currArea = (right - left + 1) * currHeight;
    18.  
    19.                 // 更新最大面积
    20.                 largestArea = (currArea > largestArea) ? currArea : largestArea;
    21.             }
    22.         }
    23.  
    24.         return largestArea;
    25.     }

    复杂度分析

    时间复杂度：O(N^2)。很明显，代码中用到了双重循环，需要耗费平方时间复杂度来做遍历计算。这个复杂度显然是比较高的。

    空间复杂度：O(1)。只用到了一些辅助变量。

    5.4 方法二：双指针

    我们可以首先遍历数组，以当前柱子的高度，作为考察的矩阵“可行高度”。然后定义左右两个指针，以当前柱子为中心向两侧探寻，找到当前高度的左右边界。

    左右边界的判断标准，就是出现了比当前高度矮的柱子，或者到达了数组边界。

    1.     // 方法二：双指针法（遍历所有可能的高度）
    2.     public int largestRectangleArea2(int[] heights){
    3.         // 定义变量保存最大面积
    4.         int largestArea = 0;
    5.  
    6.         // 遍历数组，以每个柱子高度作为最终矩形的高度
    7.         for (int i = 0; i < heights.length; i++){
    8.             // 保存当前高度
    9.             int height = heights[i];
    10.  
    11.             // 定义左右指针
    12.             int left = i, right = i;
    13.  
    14.             // 寻找左边界，左指针左移
    15.             while (left >= 0){
    16.                 if (heights[left] < height) break;
    17.                 left --;
    18.             }
    19.             // 寻找右边界，右指针右移
    20.             while (right < heights.length){
    21.                 if (heights[right] < height) break;
    22.                 right ++;
    23.             }
    24.  
    25.             // 计算当前宽度
    26.             int width = right - left - 1;
    27.  
    28.             // 计算面积
    29.             int currArea = height * width;
    30.             largestArea = (currArea > largestArea) ? currArea : largestArea;
    31.         }
    32.  
    33.         return largestArea;
    34.     }

    复杂度分析

    时间复杂度：O(N^2)。尽管少了一重循环，但在内部依然要去暴力寻找左右边界，这个操作最好情况下时间复杂度为O(1)，最坏情况下为O(N)，平均为O(N)。所以整体的平均时间复杂度仍然是O(N^2)。

    空间复杂度：O(1)。只用到了一些辅助变量。

    5.5 方法三：双指针优化

    在双指针法寻找左右边界的过程中我们发现，如果当前柱子比前一个柱子高，那么它的左边界就是前一个柱子；如果比前一个柱子矮，那么可以跳过之前确定更高的那些柱子，直接从前一个柱子的左边界开始遍历。

    这就需要我们记录下每一个柱子对应的左边界，这可以单独用一个数组来保存。

    1.     // 方法三：双指针法改进
    2.     public int largestRectangleArea3(int[] heights){
    3.         // 定义变量保存最大面积
    4.         int largestArea = 0;
    5.  
    6.         // 定义两个数组，保存每个柱子对应的左右边界
    7.         int n = heights.length;
    8.         int[] lefts = new int[n];
    9.         int[] rights = new int[n];
    10.  
    11.         // 遍历数组，计算左边界
    12.         for (int i = 0; i < n; i++) {
    13.             // 保存当前高度
    14.             int height = heights[i];
    15.  
    16.             // 定义左指针
    17.             int left = i - 1;
    18.  
    19.             // 左指针左移，寻找左边界
    20.             while (left >= 0){
    21.                 if (heights[left] < height) break;
    22.                 left = lefts[left];    // 如果左边柱子更高，就直接跳到它的左边界柱子再判断
    23.             }
    24.  
    25.             lefts[i] = left;
    26.         }
    27.  
    28.         // 遍历数组，计算右边界
    29.         for (int i = n - 1; i >= 0; i--) {
    30.             // 保存当前高度
    31.             int height = heights[i];
    32.  
    33.             // 定义右指针
    34.             int right = i + 1;
    35.  
    36.             // 右指针右移，寻找右边界
    37.             while (right < n){
    38.                 if (heights[right] < height) break;
    39.                 right = rights[right];    // 如果右边柱子更高，就直接跳到它的右边界柱子再判断
    40.             }
    41.  
    42.             rights[i] = right;
    43.         }
    44.  
    45.         // 遍历所有柱子，计算面积
    46.         for (int i = 0; i < n; i++){
    47.             int currArea = (rights[i] - lefts[i] - 1) * heights[i];
    48.             largestArea = (currArea > largestArea) ? currArea : largestArea;
    49.         }
    50.  
    51.         return largestArea;
    52.     }

    复杂度分析

    时间复杂度：O(N)。我们发现，while循环内的判断比对总体数量其实是有限的。每次比对，或者是遍历到一个新元素的时候，或者是之前判断发现当前柱子较矮，需要继续和前一个柱子的左边界进行比较。所以总的时间复杂度是O(N)。

    空间复杂度：O(N)。用到了长度为n的数组来保存左右边界。

    5.6 方法四：使用单调栈

    从上面的算法中我们可以发现，“找左边界”最重要的，其实就是排除左侧不可能的那些元素，跳过它们不再遍历。

    所以我们可以考虑用这样一个数据结构，来保存当前的所有“候选左边界”。

    当遍历到一个高度时，就让它和“候选列表”中的高度比较：如果发现它比之前的候选大，可以直接追加在后面；而如果比之前的候选小，就应该删除之前更大的候选。最终，保持一个按照顺序、单调递增的候选序列。

    过程中应该按照顺序，先比对最新的候选、再比对较老的候选。显然，我们可以用一个栈来实现这样的功能。

    栈中存放的元素具有单调性，这就是经典的数据结构单调栈了。

    我们用一个具体的例子 [6,7,5,2,4,5,9,3] 来理解单调栈。

    我们需要求出每一根柱子的左侧且最近的小于其高度的柱子。初始时的栈为空。

    （1）我们枚举 6，因为栈为空，所以 6 左侧的柱子是“哨兵”，位置为 -1。随后我们将 6 入栈。

    栈：[6(0)]。（这里括号内的数字表示柱子在原数组中的位置索引）

    （2）我们枚举 7，由于 6<7，因此不会移除栈顶元素，所以 7 左侧的柱子是 6，位置为 0。随后我们将 7 入栈。

    栈：[6(0), 7(1)]

    （3）我们枚举 5，由于 7≥5，因此移除栈顶元素 7。同样地， 6≥5，再移除栈顶元素 6。此时栈为空，所以 5 左侧的柱子是「哨兵」，位置为−1。随后我们将 5 入栈。

    栈：[5(2)]

    （4）接下来的枚举过程也大同小异。我们枚举 2，移除栈顶元素 5，得到 2 左侧的柱子是「哨兵」，位置为 −1。将 2 入栈。

    栈：[2(3)]

    （5）我们枚举 4，5 和 9，都不会移除任何栈顶元素，得到它们左侧的柱子分别是2，4 和 5，位置分别为 3，4 和 5。将它们入栈。

    栈：[2(3), 4(4), 5(5), 9(6)]

    （6）我们枚举 3，依次移除栈顶元素 9，5 和 4，得到 3 左侧的柱子是 2，位置为 3。将 3 入栈。

    栈：[2(3), 3(7)]

    这样一来，我们得到它们左侧的柱子编号分别为 [−1,0,−1,−1,3,4,5,3]。

    用相同的方法，我们从右向左进行遍历，也可以得到它们右侧的柱子编号分别为 [2,2,3,8,7,7,7,8]，这里我们将位置 8 看作右侧的“哨兵”。

    在得到了左右两侧的柱子之后，我们就可以计算出每根柱子对应的左右边界，并求出答案了。

    1.     // 方法四：单调栈
    2.     public int largestRectangleArea4(int[] heights){
    3.         // 定义变量保存最大面积
    4.         int largestArea = 0;
    5.  
    6.         // 定义两个数组，保存每个柱子对应的左右边界
    7.         int n = heights.length;
    8.         int[] lefts = new int[n];
    9.         int[] rights = new int[n];
    10.  
    11.         // 定义一个栈
    12.         Stack stack = new Stack<>();
    13.  
    14.         // 遍历所有柱子，作为当前高度，先找左边界
    15.         for (int i = 0; i < n ; i ++){
    16.             while ( !stack.isEmpty() && heights[stack.peek()] >= heights[i] ){
    17.                 stack.pop();
    18.             }
    19.  
    20.             // 所有大于等于当前高度的元素全部弹出，找到了左边界
    21.             lefts[i] = stack.isEmpty() ? -1 : stack.peek();
    22.  
    23.             stack.push(i);
    24.         }
    25.  
    26.         stack.clear();
    27.  
    28.         // 遍历所有柱子，作为当前高度，寻找右边界
    29.         for (int i = n - 1; i >= 0; i --){
    30.             while ( !stack.isEmpty() && heights[stack.peek()] >= heights[i] ){
    31.                 stack.pop();
    32.             }
    33.  
    34.             // 所有大于等于当前高度的元素全部弹出，找到了左边界
    35.             rights[i] = stack.isEmpty() ? n : stack.peek();
    36.  
    37.             stack.push(i);
    38.         }
    39.  
    40.         // 遍历所有柱子，计算面积
    41.         for (int i = 0; i < n; i++){
    42.             int currArea = (rights[i] - lefts[i] - 1) * heights[i];
    43.             largestArea = (currArea > largestArea) ? currArea : largestArea;
    44.         }
    45.  
    46.         return largestArea;
    47.     }

    复杂度分析

    时间复杂度：O(N)。每一个位置元素只会入栈一次（在枚举到它时），并且最多出栈一次。因此当我们从左向右/从右向左遍历数组时，对栈的操作的次数就为 O(N)。所以单调栈的总时间复杂度为 O(N)。

    空间复杂度：O(N)。用到了单调栈，大小为O(N)。

    5.7 方法五：单调栈优化

    当一个柱子高度比栈顶元素小时，我们会弹出栈顶元素，这就说明当前柱子就是栈顶元素对应柱子的右边界。所以我们可以只遍历一次，就求出答案。

    1.     // 方法五：单调栈优化
    2.     public int largestRectangleArea(int[] heights){
    3.         // 定义变量保存最大面积
    4.         int largestArea = 0;
    5.  
    6.         // 定义两个数组，保存每个柱子对应的左右边界
    7.         int n = heights.length;
    8.         int[] lefts = new int[n];
    9.         int[] rights = new int[n];
    10.  
    11.         // 初始化rights为右哨兵n
    12.         for (int i = 0; i < n; i ++) rights[i] = n;
    13.  
    14.         // 定义一个栈
    15.         Stack stack = new Stack<>();
    16.  
    17.         // 遍历所有柱子，作为当前高度，先找左边界
    18.         for (int i = 0; i < n ; i ++){
    19.             while ( !stack.isEmpty() && heights[stack.peek()] >= heights[i] ){
    20.                 // 栈顶元素如果小于当前元素，那么它的右边界就是当前元素
    21.                 rights[stack.peek()] = i;
    22.                 stack.pop();
    23.             }
    24.  
    25.             // 所有大于等于当前高度的元素全部弹出，找到了左边界
    26.             lefts[i] = stack.isEmpty() ? -1 : stack.peek();
    27.  
    28.             stack.push(i);
    29.         }
    30.  
    31.         // 遍历所有柱子，计算面积
    32.         for (int i = 0; i < n; i++){
    33.             int currArea = (rights[i] - lefts[i] - 1) * heights[i];
    34.             largestArea = (currArea > largestArea) ? currArea : largestArea;
    35.         }
    36.  
    37.         return largestArea;
    38.     }

    复杂度分析

    时间复杂度：O(N)。只有一次遍历，同样每个位置入栈一次、最多出栈一次。

    空间复杂度：O(N)。用到了单调栈，大小为O(N)。

  • 相关阅读:
    Boost库学习笔记（二）算法模块-C++11标准
    C#绘制带控制点的Bezier曲线，用于点阵图像及矢量图形
    虹科分享 | 麦氏比浊仪在药敏试验中的应用
    轻松入门网络爬虫-LightProxy抓包工具
    SQL监控工具
    最新微信小程序反编译方法
    element-plus 表格-合并单元格
    day61 layui和分页原理
    实现Loading倒影效果-webkit-box-reflect
    计算机毕业设计Java教师科研成果管理(源码+系统+mysql数据库+lw文档)
  • 原文地址：https://blog.csdn.net/weixin_42405670/article/details/125834929