1. 双端队列

双端队列：是一个两端都是结尾的队列。双端队列的入队和出队操作，在两端都可以进行

它与双向链表有些相似，二者的区别在于，双端队列只能在队头和队尾进行入队、出队操作，而双向链表可以在任意位置进行结点的插入和删除

1.1 实现双端队列

1.1.1 数据结构

实现双端队列的数据结构和初始化方法：

  1. class DoubleEndedQueue<Element>{
  3.     fileprivate class Node<T> : Equatable {
  5.         static func == (lhs: DoubleEndedQueue<Element>.Node<T>, rhs: DoubleEndedQueue<Element>.Node<T>) -> Bool {
  6.             let obj1 = Unmanaged<AnyObject>.passUnretained(lhs).toOpaque();
  7.             let obj2 = Unmanaged<AnyObject>.passUnretained(rhs).toOpaque();
  9.             return obj1 == obj2;
  10.         }
  12.         var prev : Node<T>?;
  13.         var next : Node<T>?;
  14.         var data : T?;
  16.         init() {}
  18.         init(data : T) {
  19.             self.data = data;
  20.             self.prev = nil;
  21.             self.next = nil;
  22.         }
  23.     }
  25.     fileprivate var _front : Node<Element>?;
  26.     fileprivate var _rear : Node<Element>?;
  27.     fileprivate var _count : Int;
  29.     init(){
  30.         _front = Node();
  31.         _rear = Node();
  33.         _front?.next = _rear;
  34.         _rear?.prev = _front;
  36.         _count = 0;
  37.     }
  39.     var length : Int {
  40.         get{
  41.             return _count;
  42.         }
  43.     }
  45.     func clear(){
  46.         _front?.next = _rear;
  47.         _rear?.prev = _front;
  48.         _count = 0;
  49.     }
  51.     func destory(){
  52.         _front = nil;
  53.         _rear = nil;
  54.         _count = 0;
  55.     }
  57.     func isEmpty() -> Bool {
  58.         return _front?.next == _rear;
  59.     }
  60. }

1.1.2 入队方法

实现队头和队尾的入队方法：

  1. class DoubleEndedQueue<Element>{
  3.     func enterWithFront(element : Element){
  4.         let node = Node(data: element);
  6.         node.next = _front?.next;
  7.         node.prev = _front;
  9.         _front?.next?.prev = node;
  10.         _front?.next = node;
  12.         _count += 1;
  13.     }
  15.     func enterWithRear(element : Element) {
  16.         let node = Node(data: element);
  18.         node.prev = _rear?.prev;
  19.         node.next = _rear;
  21.         _rear?.prev?.next = node;
  22.         _rear?.prev = node;
  24.         _count += 1;
  25.     }
  26. }

1.1.3 出队方法

实现队头和队尾的出队方法：

  1. class DoubleEndedQueue<Element>{
  3.     func outWithFront() -> Element?{
  5.         if(isEmpty()){
  6.             return nil;
  7.         }
  9.         let node = _front!.next!;
  10.         return out(node: node);
  11.     }
  13.     func outWithRear() -> Element?{
  15.         if(isEmpty()){
  16.             return nil;
  17.         }
  19.         let node = _rear!.prev!;
  20.         return out(node: node);
  21.     }
  23.     fileprivate func out(node : Node<Element>) -> Element {
  25.         node.prev?.next = node.next;
  26.         node.next?.prev = node.prev;
  28.         _count -= 1;
  30.         return node.data!;
  31.     }
  32. }

1.1.4 获取元素

分别从队头和队尾获取元素：

  1. class DoubleEndedQueue<Element>{
  3.     func peekWithFront() -> Element?{
  5.         if(isEmpty()){
  6.             return nil;
  7.         }
  9.         return _front?.next?.data;
  10.     }
  12.     func peekWithRear() -> Element?{
  14.         if(isEmpty()){
  15.             return nil;
  16.         }
  18.         return _rear?.prev?.data;
  19.     }
  20. }

1.1.5 打印方法

实现队列的打印方法：

  1. class DoubleEndedQueue<Element>{
  3.     func traverseWithFront() -> String {
  5.         var str : String = "";
  7.         if(isEmpty()){
  8.             return str;
  9.         }
  11.         var node = _front?.next;
  13.         while(node != _rear){
  14.             str += "\(node!.data!),"
  15.             node = node?.next;
  16.         }
  18.         return str;
  19.     }
  21.     func traverseWithRear() -> String {
  23.         var str : String = "";
  25.         if(isEmpty()){
  26.             return str;
  27.         }
  29.         var node = _rear?.prev;
  31.         while(node != _front){
  32.             str += "\(node!.data!),"
  33.             node = node?.prev;
  34.         }
  36.         return str;
  37.     }
  38. }

1.2 翻转字符串里的单词

给出一个字符串s，逐个翻转字符串中的所有单词

单词是由非空格字符组成的字符串。s中使用至少一个空格将字符串中的单词分隔开

请返回一个翻转s中单词顺序并用单个空格相连的字符串

说明：

  • 输入字符串s可以在前面、后面或者单词间包含多余的空格

  • 翻转后单词间应当仅用一个空格分隔

  • 翻转后的字符串中不应包含额外的空格

示例1：

  1. 输入：s = "the sky is blue"
  2. 输出："blue is sky the"

示例2：

  1. 输入：s = "  hello world  "
  2. 输出："world hello"
  • 输入字符串可以在前面或者后面包含多余的空格，但是翻转后的字符不能包括

示例3：

  1. 输入：s = "a good   example"
  2. 输出："example good a"
  • 如果两个单词间有多余的空格，将翻转后单词间的空格减少到只含一个

示例4：

  1. 输入：s = "  Bob    Loves  Alice   "
  2. 输出："Alice Loves Bob"

示例5：

  1. 输入：s = "Alice does not even like bob"
  2. 输出："bob like even not does Alice"

1.2.1 栈结构实现

遍历字符串，当前字符非空格，存储到tmp临时变量中。如果当前字符为空格，或者遍历到字符串结尾，此时tmp不为空，将其入栈，并且将tmp清空

当符合入栈条件时，tmp为空，证明遇到了连续空格，所以不需要入栈

最后进行栈的遍历，将元素依次出栈，并拼接为完整字符串，将其返回即可

代码实现：

  1. class Solution {
  3.     var stack : LinkedStack<String>;
  5.     init(){
  6.         stack = LinkedStack<String>();
  7.     }
  9.     func reverseWords(_ s: String) -> String {
  11.         var tmp = "";
  13.         for i in 0..<s.count {
  15.             let c = s[i];
  17.             if(c != " "){
  18.                 tmp += "\(c)";
  19.             }
  21.             if(!tmp.isEmpty && (c == " " || i == s.count - 1)){
  22.                 stack.push(element: tmp);
  23.                 tmp = "";
  24.             }
  25.         }
  27.         var str = "";
  29.         while(!stack.isEmpty()){
  31.             if(!str.isEmpty){
  32.                 str += " ";
  33.             }
  35.             str += stack.pop()!;
  36.         }
  38.         return str;
  39.     }
  40. }

1.2.2 双端队列实现

翻转字符串的逻辑不变，只是将栈结构换成双端队列。字符串从队尾入队，遍历元素时，再将字符串从队尾出队，达到翻转效果

代码实现：

  1. class Solution {
  3.     var queue : DoubleEndedQueue<String>;
  5.     init(){
  6.         queue = DoubleEndedQueue<String>();
  7.     }
  9.     func reverseWords(_ s: String) -> String {
  11.         var tmp = "";
  13.         for i in 0..<s.count {
  15.             let c = s[i];
  17.             if(c != " "){
  18.                 tmp += "\(c)";
  19.             }
  21.             if(!tmp.isEmpty && (c == " " || i == s.count - 1)){
  22.                 queue.enterWithRear(element: tmp);
  23.                 tmp = "";
  24.             }
  25.         }
  27.         var str = "";
  29.         while(!queue.isEmpty()){
  31.             if(!str.isEmpty){
  32.                 str += " ";
  33.             }
  35.             str += queue.outWithRear()!;
  36.         }
  38.         return str;
  39.     }
  40. }

2. 单调队列

单调队列：和普通双端队列相比，队列中的元素全部按照单调递减或递增的

  • 单调递增队列：保证队列头元素一定是当前队列的最小值，用于维护区间的最小值

  • 单调递减队列：保证队列头元素一定是当前队列的最大值，用于维护区间的最大值

队列的特点：队头和队尾都可以进行出队操作，但只有队尾可以进行入队操作

新元素入队时，如果从队尾插入后会破坏单调性，则删除队尾元素，直到插入后不再破坏单调性为止，再将其插入单调队列

2.1 实现单调队列

2.1.1 数据结构

实现单调队列的数据结构和初始化方法：

  1. class MonotoneQueue<Element : Comparable>{
  3.     fileprivate class Node<T> : Equatable {
  5.         static func == (lhs: MonotoneQueue<Element>.Node<T>, rhs: MonotoneQueue<Element>.Node<T>) -> Bool {
  6.             let obj1 = Unmanaged<AnyObject>.passUnretained(lhs).toOpaque();
  7.             let obj2 = Unmanaged<AnyObject>.passUnretained(rhs).toOpaque();
  9.             return obj1 == obj2;
  10.         }
  12.         var prev : Node<T>?;
  13.         var next : Node<T>?;
  14.         var data : T?;
  16.         init() {}
  18.         init(data : T) {
  19.             self.data = data;
  20.             self.prev = nil;
  21.             self.next = nil;
  22.         }
  23.     }
  25.     fileprivate var _front : Node<Element>?;
  26.     fileprivate var _rear : Node<Element>?;
  27.     fileprivate var _count : Int;
  29.     init(){
  30.         _front = Node();
  31.         _rear = Node();
  33.         _front?.next = _rear;
  34.         _rear?.prev = _front;
  36.         _count = 0;
  37.     }
  39.     var length : Int {
  40.         get{
  41.             return _count;
  42.         }
  43.     }
  45.     func clear(){
  46.         _front?.next = _rear;
  47.         _rear?.prev = _front;
  48.         _count = 0;
  49.     }
  51.     func destory(){
  52.         _front = nil;
  53.         _rear = nil;
  54.         _count = 0;
  55.     }
  57.     func isEmpty() -> Bool {
  58.         return _front?.next == _rear;
  59.     }
  60. }

2.1.2 入队方法

实现入队方法，必须保证不能破坏单调性：

  1. class MonotoneQueue<Element : Comparable>{
  3.     func enterWithIncreasing(element : Element){
  5.         while(!isEmpty()){
  7.             if(peekWithRear()! <= element){
  8.                 break;
  9.             }
  11.             outWithRear();
  12.         }
  14.         enter(element: element);
  15.     }
  17.     func enterWithDecrease(element : Element) {
  19.         while(!isEmpty()){
  21.             if(peekWithRear()! >= element){
  22.                 break;
  23.             }
  25.             outWithRear();
  26.         }
  28.         enter(element: element);
  29.     }
  31.     fileprivate func enter(element : Element) {
  33.         let node = Node(data: element);
  35.         node.prev = _rear?.prev;
  36.         node.next = _rear;
  38.         _rear?.prev?.next = node;
  39.         _rear?.prev = node;
  41.         _count += 1;
  42.     }
  43. }

2.1.3 出队方法

实现队头和队尾的出队方法：

  1. class MonotoneQueue<Element : Comparable>{
  3.     func outWithFront() -> Element?{
  5.         if(isEmpty()){
  6.             return nil;
  7.         }
  9.         let node = _front!.next!;
  10.         return out(node: node);
  11.     }
  13.     func outWithRear() -> Element?{
  15.         if(isEmpty()){
  16.             return nil;
  17.         }
  19.         let node = _rear!.prev!;
  20.         return out(node: node);
  21.     }
  23.     fileprivate func out(node : Node<Element>) -> Element {
  25.         node.prev?.next = node.next;
  26.         node.next?.prev = node.prev;
  28.         _count -= 1;
  30.         return node.data!;
  31.     }
  32. }

2.1.4 获取元素

分别从队头和队尾获取元素：

  1. class MonotoneQueue<Element : Comparable>{
  3.     func peekWithFront() -> Element?{
  5.         if(isEmpty()){
  6.             return nil;
  7.         }
  9.         return _front?.next?.data;
  10.     }
  12.     func peekWithRear() -> Element?{
  14.         if(isEmpty()){
  15.             return nil;
  16.         }
  18.         return _rear?.prev?.data;
  19.     }
  20. }

2.1.5 打印方法

实现队列的打印方法：

  1. class MonotoneQueue<Element : Comparable>{
  3.     func traverseWithFront() -> String {
  5.         var str : String = "";
  7.         if(isEmpty()){
  8.             return str;
  9.         }
  11.         var node = _front?.next;
  13.         while(node != _rear){
  14.             str += "\(node!.data!),"
  15.             node = node?.next;
  16.         }
  18.         return str;
  19.     }
  21.     func traverseWithRear() -> String {
  23.         var str : String = "";
  25.         if(isEmpty()){
  26.             return str;
  27.         }
  29.         var node = _rear?.prev;
  31.         while(node != _front){
  32.             str += "\(node!.data!),"
  33.             node = node?.prev;
  34.         }
  36.         return str;
  37.     }
  38. }

2.2 滑动窗口最大值

给出一个整数数组nums，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k个数字

滑动窗口每次只向右移动一位，我们要返回滑动窗口中的最大值

示例1：

  1. 输入：nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
  2. 输出：[3, 3, 5, 5, 6, 7]
  3. 解释：滑动窗口的位置最大值
  4. ----------------------------------------
  5. [1  3  -1] -3  5  3  6  7       3
  6.  1 [3  -1  -3] 5  3  6  7       3
  7.  1  3 [-1  -3  5] 3  6  7       5
  8.  1  3  -1 [-3  5  3] 6  7       5
  9.  1  3  -1  -3 [5  3  6] 7       6
  10.  1  3  -1  -3  5 [3  6  7]      7

示例2：

  1. 输入：nums = [1], k = 1
  2. 输出：[1]

2.2.1 单调队列实现

遍历nums，将元素加入到单调递减队列中。当i >= k - 1时，说明加入队列的数据达到了窗口的限制，此时应获取队列头元素，即当前窗口中的最大值，然后将其加入到结果数组中

当窗口移动时，窗口中的数据会时时变化。所以在获得本次结果之后，应该提前删除队列中即将滑出窗口的数据。判断依据：如果队列头元素与nums[i - k + 1]相等，说明本次窗口中的最大值，就是即将滑出窗口的数据，提前将其从队列的头部出队

📢 注意：在实现单调递减队列时，我们判断队尾元素 >= 新元素即可入队。其中的>=很重要，由于元素在相等的情况下也能入队，避免了即将滑出窗口的数据和队列中下一个元素相等时的误删情况

代码实现：

  1. class Solution {
  3.     func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {
  5.         let queue = MonotoneQueue<Int>();
  6.         var result = [Int]();
  8.         for i in 0..<nums.count {
  10.             queue.enterWithDecrease(element: nums[i]);
  12.             if(i < k - 1){
  13.                 continue;
  14.             }
  16.             var max = queue.peekWithFront()!;
  17.             result.append(max);
  19.             if(max == nums[i - k + 1]){
  20.                 queue.outWithFront();
  21.             }
  22.         }
  24.         return result;
  25.     }
  26. }

2.2.2 双索引实现

我们可以使用monotoneQueue数组代替单调队列，定义left和right双索引，left表示当前窗口中最大值的索引值，right表示当前窗口中最小值的索引值

遍历nums，获得当前元素。遍历monotoneQueue数组，如果队尾元素小于当前元素，依次将队尾元素出队，即right -= 1。只有在队尾元素大于等于当前元素的情况下，将当前元素入队，同时right += 1

当i >= k - 1时，说明加入队列的数据达到了窗口的限制，此时应获取队列头元素，即当前窗口中的最大值，然后将其加入到结果数组中

如果队列头元素与nums[i - k + 1]相等，说明该元素即将滑出窗口，提前将其从队列的头部出队，即left += 1

📢 注意：单调队列中元素的出队条件，一定是队尾元素小于当前元素，不能使用小于等于。如果元素在相等的情况下就出队，在后面判断元素即将滑出窗口时，会造成误删除的情况

代码实现：

  1. class Solution {
  3.     func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {
  5.         // 记录结果的数组
  6.         var result = [Int]();
  7.         // 当前窗口中最大值的索引值
  8.         var left = 0;
  9.         // 当前窗口中最小值的索引值
  10.         var right = 0;
  11.         // 代替单调队列的数组
  12.         var monotoneQueue = [Int].init(repeating: 0, count: nums.count);
  14.         // 遍历nums
  15.         for i in 0..<nums.count {
  17.             // 获得当前元素
  18.             let num = nums[i];
  20.             // 判断队尾元素是否小于当前元素
  21.             while(left < right && monotoneQueue[right - 1] < nums[i]){
  22.                 // 如果小于，依次将队尾元素出队。不能破坏队列的单调性
  23.                 right -= 1;
  24.             }
  26.             // 在队尾元素大于等于当前元素的情况下，将当前元素入队
  27.             monotoneQueue[right] = num;
  28.             right += 1;
  30.             // 判断加入队列的数据是否达到了窗口的限制
  31.             if(i < k - 1){
  32.                 // 未达到，跳出循环
  33.                 continue;
  34.             }
  36.             // 达到窗口的限制，获取当前窗口中的最大值
  37.             let max = monotoneQueue[left];
  38.             // 将其加入到结果数组中
  39.             result.append(max);
  41.             // 判断该元素，是否为即将滑出窗口的元素
  42.             if(max == nums[i - k + 1]){
  43.                 // 如果是，提前将其从队列的头部出队
  44.                 left += 1;
  45.             }
  46.         }
  48.         return result;
  49.     }
  50. }

总结

双端队列：

  • 一个两端都是结尾的队列。双端队列的入队和出队操作，在两端都可以进行

  • 它与双向链表有些相似，二者的区别在于，双端队列只能在队头和队尾进行入队、出队操作，而双向链表可以在任意位置进行结点的插入和删除

单调队列：

  • 和普通双端队列相比，队列中的元素全部按照单调递减或递增的

    • 单调递增队列：保证队列头元素一定是当前队列的最小值，用于维护区间的最小值

    • 单调递减队列：保证队列头元素一定是当前队列的最大值，用于维护区间的最大值

  • 队列的特点：队头和队尾都可以进行出队操作，但只有队尾可以进行入队操作

    • 新元素入队时，如果从队尾插入后会破坏单调性，则删除队尾元素，直到插入后不再破坏单调性为止，再将其插入单调队列