学剑篇：基本数据结构

发现labuladong算法秘籍真的不错，已经跟着刷了一段时间题了，打算总结一下，先从第一篇学剑开始吧！加油！具体可以参考原网站

原论文为Java版本，我这里选择用C++实现，同时记录自己的一些思考

1.1 数组+链表

田忌赛马背后的算法决策：

例题：870. 优势洗牌

• 解题思路：

  • 如果当前最快的马可以比过对方最快的马，则用该马来比赛
    • 误区：如果第二快的马也可以比过对方，是否可以选择这一匹来比？可以但没必要，因为这样的话我最快的一匹还是比对方第二最快的马快
  • 如果当前最快的马比不过对方最快的马，则用最烂的一匹来比

• 实现trike：

  • 因为nums2不能改变顺序，但又需要他从大到小排列（方便后面比较），因此选用priority_queue来重新存储nums2，但这里需要把下标i以及数值num一起存储，并且用num来比大小，因此需要重载operator<运算符
  • nums1也要排序，这里选用升序排序，left为最小值，right为最大值
  • 双指针来收缩nums1的两端，如果nums2当前最大值大于nums1[right]，则用left对应的马，反之则用right对应的马

• 代码：

  class Solution {
  public:
      vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) 
      {
          // 定义结构体：用来自定义优先队列比较规则
          struct id_nums2
          {
              int i;
              int num;
              id_nums2(int j, int x)
              {
                  i = j;
                  num = x;
              }
              bool operator<(const id_nums2& a) const
              {
                  return num < a.num; // 大顶堆
              }
          };
          // 对nums2数组建立优先队列
          priority_queue<id_nums2> nums2pq;
          for(int i=0; i<nums2.size(); ++i)
          {
              nums2pq.push(id_nums2(i, nums2[i]));
          }
          // 双指针
          int left = 0, right = nums1.size()-1;
          vector<int> res(nums1.size(), 0);
          sort(nums1.begin(), nums1.end()); // 从小到大排序
          while(left<=right)
          {
              int i = nums2pq.top().i;
              int num = nums2pq.top().num;
              nums2pq.pop();
              // nums1能打过
              if(nums1[right]>num)
              {
                  res[i] = nums1[right];
                  right--;
              }
              else
              {
                  res[i] = nums1[left];
                  left++;
              }
          }
          return res;
  
      }
  };

• 复杂度分析：前期排序为O(nlogn)，后续仅遍历一次队列，时间复杂度为O(nlogn)，因为共n个元素，调整最大堆的复杂度为O(logn)，其他操作为O(1)，因此时间复杂度为O(nlogn)。空间复杂度为O(n)因为需要新开辟优先队列和res

链表操作的递归思维一览：用递归不用迭代

例题：206. 反转链表

• 解题思路：

  • reverse函数：输入一个节点head，将以head为起点的链表反转，并返回反转后的头节点

• 解题tricks：

  • 不要跳进递归，而是要根据刚才的函数定义，来弄清楚这段代码会产生什么结果

• 代码：

  /**
   * Definition for singly-linked list.
   * struct ListNode {
   *     int val;
   *     ListNode *next;
   *     ListNode() : val(0), next(nullptr) {}
   *     ListNode(int x) : val(x), next(nullptr) {}
   *     ListNode(int x, ListNode *next) : val(x), next(next) {}
   * };
   */
  class Solution {
  public:
      ListNode* reverse(ListNode* head)
      {
          if(head == NULL || head->next == NULL)
          {
              return head;
          }
          ListNode* last = reverse(head->next);
          head->next->next = head;
          head->next = NULL;
          return last;
      }
      ListNode* reverseList(ListNode* head) 
      {
          return reverse(head);
      }
  };

• 复杂度分析：只遍历一遍链表，因此时间复杂度为O(n)，空间复杂度为O(n)，因为递归的底层实现是栈，而栈的大小是n（压入所有的节点）

例题：92. 反转链表 II

• 解题思路：

  • 先尝试解决反转前N个node
  • 定义reverseN(head, N)函数，输入节点head，以及要反转的节点个数N，返回前N个节点反转，后面节点顺序不变的链表的链表头

• 解题tricks：

  • 定义successor，用来指向要反转的最后一个node的下一个node，好把第一个node指向successor上。
  • 在left不等于1时，反复调用原函数，使得head向后移动的同时，缩小left和right，当left为1时再调用reversN函数，最后将head->next指向reverseN的返回值（链表头）

• 代码：

  /**
   * Definition for singly-linked list.
   * struct ListNode {
   *     int val;
   *     ListNode *next;
   *     ListNode() : val(0), next(nullptr) {}
   *     ListNode(int x) : val(x), next(nullptr) {}
   *     ListNode(int x, ListNode *next) : val(x), next(next) {}
   * };
   */
  class Solution {
  public:
      ListNode *successor = NULL;
      ListNode* reverseN(ListNode* head, int m) // 反转前M个节点，并返回反转后链表的头节点
      {
          if(m == 1) 
          {
              successor = head->next;
              return head;
          }
          ListNode* last = reverseN(head->next, m-1);
          head->next->next = head;
          head->next = successor;
          return last;
      }
      ListNode* reverseBetween(ListNode* head, int left, int right) 
      {
          if(left == 1) return reverseN(head, right); // 从left节点开始反转
          head->next = reverseBetween(head->next, left-1, right-1);
          return head;
      }
  };

• 复杂度分析：只遍历一遍，时间复杂度为O(n)，空间复杂度为O(n)

1.3 队列&栈

用栈解决“括号问题”

例题1：20. 有效的括号

• 解题思路：

  • 如果仅有一种括号，只用记录左括号的数量即可
  • 但多种括号时，无法通过计数来完成，比如"([)]"是不合法的，此时需要借助栈（后进先出）来完成
  • 当输入为左括号时，压入栈中；当输入为右括号时，比较栈顶和右括号是否匹配
    • 匹配时，pop出栈顶元素
    • 不匹配或栈为空时，return false

• 解题tricks：

  • 遍历字符串：

    方法一：
    for(int i=0; i<s.size(); ++i)
    {
        s[i];
    }
    方法二：auto类型
    for(auto c:s)
    {
        c;
    }

• 代码：

  class Solution {
  public:
      bool isValid(string s) 
      {
          stack<char> left;
          for(int i=0; i<s.size(); ++i)
          {
              if(s[i]=='(' || s[i]=='[' || s[i]=='{') left.push(s[i]);
              else
              {
                  if(left.empty()) return false;
                  if((s[i]==')' && left.top()=='(') 
                     || (s[i]==']' && left.top()=='[') 
                     || (s[i]=='}' && left.top()=='{')) 
                      left.pop();
                  else return false;
              }
          }
          return left.empty();
      }
  };

• 复杂度分析：时间复杂度为O(N)，空间复杂度为O(N)

921. 使括号有效的最少添加

• 解题思路：

  • 思路一：用栈来解决，碰到不匹配时说明左括号不够用，当最后结束时栈没空，证明左括号太多了
  • 思路二：不用栈，用两个变量记录左括号的数量以及res即可，思路同上

• 解题tricks：最后要记得加上栈中残留的左括号

• 代码：

  class Solution {
  public:
      int minAddToMakeValid(string s) 
      {
          stack<char> left;
          int res = 0;
          for(char c:s)
          {
              if(c=='(') left.push(c);
              else
              {
                  if(left.empty()) res++;
                  else
                  {
                      left.pop();
                  }
              }
          }
          res += left.size();
          return res;
      }
  };

• 复杂度分析：时间空间复杂度均为O(N)，但空间复杂度可以降到O(1)

1541. 平衡括号字符串的最少插入次数 1个左括号和2个右括号匹配

• 解题思路：

  • 不用栈：left记录当前有多少个左括号，以及res目前添加了多少个括号了
    • 如果当前为左括号，left++
    • 如果为右括号
      • 判断当前左括号是否为空，空的话则在当前位置左侧添加一个左括号
      • 不为空时，判断当前位置的下一个位置是否为右括号
        • 如果是，则不用添加任何操作，把left--，然后i++（跳过下一个位置）
        • 如果不是，则需要在后侧加入一个右括号，即res++，同时减去匹配的左括号left--
    • 最后剩下的左括号需要用2倍的右括号来匹配
  • 用栈：也可以完成

• 解题tricks：

• 代码：

  class Solution {
  public:
      int minInsertions(string s) 
      {
          int left=0, res=0;
          for(int i=0; i<s.size(); ++i)
          {
              if(s[i] == '(') left++;
              else
              {
                  if(left==0)
                  {
                      res++;
                      left++;
                  }
                  if(s[i+1]==')') 
                  {
                      left--;
                      i++;
                  }
                  else if(s[i+1]=='(' || i==s.size()-1)
                  {
                      res++;
                      left--;
                  }
              }
          }
          return res + 2*left;
      }
  };

• 复杂度分析：时间复杂度为O(N)，空间为O(1)

单调栈结构解决“下一个更大数问题”

单调栈解决的就是The Next Greater Number问题，适用范围还是比较窄的，但是遇到这类问题就要用这个方法

• 模板：

  stack<int> s;
  // 从后向前遍历数组
  for(int i=nums.size()-1; i>=0; --i) // 当有循环数组出现时，可以遍历两遍，用%符号
  {
      while(!s.empty() && nums[i]>=s.top()) // 如果当前值小于栈顶值，则压入栈，否则pop栈顶元素
      {
          s.pop();
      }
      res[i] = s.empty()? -1:s.top(); // 这里res存储nums的值，其实有些题目也可以存储下标
      s.push(nums[i]);
  }

496. 下一个更大元素 I

• 解题思路：

  • 建立单调栈，先把nums2中的数组从后向前遍历，同时将数值压入栈中，使栈呈现由大到小的排列，此时栈顶即为下一个更大的元素

• 解题tricks：

  • 用哈希表来存储<数值，下一个更大元素值>，这样遍历nums1时就可以直接找到对应的答案了

• 代码：

  class Solution {
  public:
      vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) 
      {
          unordered_map<int, int> hm;
          vector<int> res(nums1.size(), -1);
          stack<int> s;
          for(int i=nums2.size()-1; i>=0; --i)
          {
              while(!s.empty() && s.top()<=nums2[i])
              {
                  s.pop();
              }
              hm[nums2[i]] = s.empty() ? -1:s.top();
              s.push(nums2[i]);
          }
          for(int i=0; i<nums1.size(); ++i)
          {
              res[i] = hm[nums1[i]];
          }
          return res;
      }
  };

• 复杂度分析：因为每个元素只会被push和pop一次，因此时间复杂度为O(n)，空间复杂度因为是栈结构，且返回值也是数值，因此为O(n)

503. 下一个更大元素 II

• 解题思路：

  • 沿用单调栈的思路，找到下一个更大的数值，但这里设计循环数组，一般这个时候可以复制一份到原数组后面，然后就可以了

• 解题tricks：没必要复制一份，可以遍历2n次，然后i用%n的值就可以达到相同的目的了

• 代码：

  class Solution {
  public:
      vector<int> nextGreaterElements(vector<int>& nums) 
      {
          int n = nums.size();
          vector<int> res(n);
          stack<int> s;
          for(int i= 2*n-1; i>=0; --i) // 假设复制了一份
          {
              while(!s.empty() && s.top()<=nums[i%n]) // 用%来求相应的坐标
              {
                  s.pop();
              }
              if(!s.empty()) res[i%n] = s.top();
              else res[i%n] = -1;
              s.push(nums[i%n]);
          }
          return res;
      }
  };

• 复杂度分析：时间空间也都是O(n)

739. 每日温度

• 解题思路：同上

• 解题tricks：栈中存储下一个更大元素的下标，这样方便计算距离，同时用下标也可以找到当日的温度

• 代码：

  class Solution {
  public:
      vector<int> dailyTemperatures(vector<int>& temperatures) 
      {
          vector<int> res(temperatures.size(), 0);
          stack<int> s; // 存放next greater number的下标
          for(int i=temperatures.size()-1; i>=0; --i)
          {
              while(!s.empty() && temperatures[s.top()]<=temperatures[i])
              {
                  s.pop();
              }
              if(!s.empty()) res[i] = s.top() - i;
              s.push(i);
          }
          return res;
      }
  };

• 复杂度分析：时间空间复杂度是O(n)

单调队列解决“滑动窗口最大值”

单调队列的实现方式使用STL中的deque类，中文是双向队列，意思是两边都可以进出，在进出的过程中保证队列是单调递减（增）的就可以

239. 滑动窗口最大值

• 解题思路：

  • 思路一：用优先队列，滑动窗口内的值和下标作为pair压入最大堆中，first为值，因为优先队列先对pair的首个元素排序。for循环在外侧遍历所有的窗口右端点，while内循环来判断最大值是否在滑动窗口内部，不在的话需要都pop出去。
  • 思路二：用单调队列，解题参考
    • 遍历给定数组中的元素，如果队列不为空且当前考察元素大于等于队尾元素，则将队尾元素移除。直到，队列为空或当前考察元素小于新的队尾元素
    • 当队首元素的下标小于滑动窗口左侧边界left时，表示队首元素已经不再滑动窗口内，因此将其从队首移除
    • 由于数组下标从0开始，因此当窗口右边界right+1大于等于窗口大小k时，意味着窗口形成。此时，队首元素就是该窗口内的最大值

• 解题tricks：

  • 优先队列priority_queue中数据类型为pair时，先对first比大小，在对second比大小
  • 双端队列deque可以从两端进行push和pop，关键字分别是back和front

• 代码：

  • 思路一：

    class Solution {
    public:
        vector<int> maxSlidingWindow(vector<int>& nums, int k) 
        {
            // 解法一：最大堆
            priority_queue<pair<int, int>> pq;
            vector<int> res;
            for(int i=0; i<nums.size(); ++i)
            {
                if(i < k-1)
                {
                    pq.push(pair(nums[i], i));
                }
                else
                {
                    pq.push(pair(nums[i], i));
                    while(pq.top().second < i-k+1)
                    {
                        pq.pop();
                    }
                    res.emplace_back(pq.top().first);
                }
            }
            return res;
        }
    };

  • 思路二：可以通过存pair来做，也可以通过存下标来完成

    class Solution {
    public:
        vector<int> maxSlidingWindow(vector<int>& nums, int k) 
        {
            // 解法二：双向队列来实现单调队列
            deque<pair<int, int>> dq; // 存储值和下标
            vector<int> res;
            for(int r=0; r<nums.size(); ++r)
            {
                while(!dq.empty() && dq.back().first <= nums[r])
                {
                    dq.pop_back();
                }
                dq.emplace_back(pair(nums[r], r));
                int l = r-k+1;
                while(!dq.empty() && dq.front().second < l)
                {
                    dq.pop_front();
                }
                if(r+1>=k)
                {
                    res.emplace_back(dq.front().first);
                }
            }
            return res;
        }
    };
    
    class Solution {
    public:
        vector<int> maxSlidingWindow(vector<int>& nums, int k) 
        {
            // 解法二：双向队列来实现单调队列
            deque<int> dq; // 只存储下标
            vector<int> res;
            for(int r=0; r<nums.size(); ++r)
            {
                while(!dq.empty() && nums[dq.back()] <= nums[r])
                {
                    dq.pop_back();
                }
                dq.emplace_back(r);
                int l = r-k+1;
                while(!dq.empty() && dq.front() < l)
                {
                    dq.pop_front();
                }
                if(r+1>=k)
                {
                    res.emplace_back(nums[dq.front()]);
                }
            }
            return res;
        }
    };

• 复杂度分析：

  • 思路一的时间复杂度为O(nlogn)，因为优先队列的调整是logn的，而遍历数组是n
  • 思路二的时间复杂度为O(n)，因为从元素的角度出发，每个元素只被push和pop了一次

“数组去重问题”

316. 去除重复字母

• 解题思路：

  • 可以将题目拆分成3个问题
    1. 去重
    2. 字符前后顺序不变
    3. 字典序最小
  • 可以尝试用栈+标记数组来解决前两个问题，即将babc变为bac
  • 再尝试修改上面的思路，在插入元素时用while和栈顶元素比大小，并将大的元素且后面还会出现的元素pop出来（后方是否还会出现需要用一个count数组在一开始遍历一下整个字符串，记录每个字符出现的次数）

• 解题triks

  • 方是否还会出现需要用一个count数组在一开始遍历一下整个字符串，记录每个字符出现的次数【在循环外多遍历一遍数组不会增加复杂度，因为遍历只有O(N)复杂度】

• 代码

  • 解决前两个问题：

    #include<algorithm>
    class Solution {
    public:
        string removeDuplicateLetters(string s) 
        {
            stack<char> S;
            vector<bool> inStack(26, false);
            for(int i=0; i<s.size(); ++i)
            {
                if(inStack[s[i]-'a'])
                {
                    continue;
                }
                S.push(s[i]);
                inStack[s[i]-'a'] = true;
            }
            string res;
            while(!S.empty())
            {
                res.push_back(S.top());
                S.pop();
            }
            reverse(res.begin(), res.end());
            return res;
        }
    };

  • 解决第三个问题

      #include<algorithm>
      class Solution {
    public:
          string removeDuplicateLetters(string s) 
          {
              stack<char> S;
              vector<int> ccount(26, 0); // 统计当前位置的后面元素的多少
              vector<char> inStack(26, false);
              for(char c : s)
              {
                  ccount[c-'a']++;
              }
      
              for(int i=0; i<s.size(); ++i)
              {
                  // 无论后面如何操作，当前的字符都--
                  ccount[s[i]-'a']--;
                  // 如果当前字符已经在里面了，那就没必要把一些元素挤出来，再push它进去了。例如abca，当第二个a来时，直接跳过即可，否则就变成了a
                  if(inStack[s[i]-'a']) continue;
      
                  // 当前值需要被插入
                  // 栈不为空，栈顶元素大于当前值，且栈顶元素在后面还会出现
                  while(!S.empty() && S.top() > s[i] && ccount[S.top()-'a'] > 0)
                  {
                      inStack[S.top()-'a'] = false;
                      S.pop();
                  }
                  // 把该pop的pop走后，再把当前元素push进来
                  S.push(s[i]); 
                  inStack[s[i]-'a'] = true;
              }
              string res;
              while(!S.empty())
              {
                  res.push_back(S.top());
                  S.pop();
              }
              reverse(res.begin(), res.end());
              return res;
          }
      };

• 复杂度分析：总共遍历了一次字符串，虽然内部有个while循环，但是所有元素只会被push和pop一次到栈内，因此时间复杂度是O(N)