鏈表問題、單調棧-LeetCode 430、725、168、1290、215、1019、503（遞減型單調棧）

• 2019 年 12 月 24 日
• 筆記

作者：TeddyZhang，公眾號：算法工程師之路

鏈表問題（三）、單調棧：

LeetCode # 430 725 168 1290 215 1019 503

1

編程題

【LeetCode #430】扁平化多級雙向鏈表

您將獲得一個雙向鏈表，除了下一個和前一個指針之外，它還有一個子指針，可能指向單獨的雙向鏈表。這些子列表可能有一個或多個自己的子項，依此類推，生成多級數據結構，如下面的示例所示。

扁平化列表，使所有結點出現在單級雙鏈表中。您將獲得列表第一級的頭部。

示例: 輸入: 1—2—3—4—5—6–NULL | 7—8—9—10–NULL | 11–12–NULL 輸出: 1-2-3-7-8-11-12-9-10-4-5-6-NULL

解題思路：

把上面的圖向左旋轉90度，就會發現其實一個二叉樹，然後這道題的實質就是二叉樹的先序遍歷，下面使用先序遍歷的迭代法，不知道大家忘了沒有。在遍歷完成的同時進行雙向鏈表的構建，由於其還有child指針，應該置為nullptr. 注意：先，中，後序遍歷都是指的根節點的訪問順序。

/*  // Definition for a Node.  class Node {  public:      int val;      Node* prev;      Node* next;      Node* child;  };  */  class Solution {  public:      Node* flatten(Node* head) {          stack<Node*> sta;          if (head == nullptr) return nullptr;          sta.push(head);          Node* pre = nullptr;          while(!sta.empty()) {              Node* tmp = sta.top();              sta.pop();              if (tmp->next != nullptr) sta.push(tmp->next);              if (tmp->child != nullptr) {   // 雙向鏈表中child為空                  sta.push(tmp->child);                  tmp->child = nullptr;              }              if(pre) {   // 構建雙向鏈表                  pre->next = tmp;                  tmp->prev = pre;              }              pre = tmp;          }          return head;      }  };  

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/flatten-a-multilevel-doubly-linked-list

【LeetCode #725】分割鏈表

給定一個頭結點為 root 的鏈表, 編寫一個函數以將鏈表分隔為 k 個連續的部分。 每部分的長度應該儘可能的相等: 任意兩部分的長度差距不能超過 1，也就是說可能有些部分為 null。 這k個部分應該按照在鏈表中出現的順序進行輸出，並且排在前面的部分的長度應該大於或等於後面的長度。 返回一個符合上述規則的鏈表的列表。 舉例：1->2->3->4, k = 5 // 5 結果 [ [1], [2], [3], [4], null ]

示例 1： 輸入: root = [1, 2, 3], k = 5 輸出: [[1],[2],[3],[],[]] 解釋: 輸入輸出各部分都應該是鏈表，而不是數組。 例如, 輸入的結點 root 的 val= 1, root.next.val = 2, root.next.next.val = 3, 且 root.next.next.next = null。 第一個輸出 output[0] 是 output[0].val = 1, output[0].next = null。 最後一個元素 output[4] 為 null, 它代表了最後一個部分為空鏈表。

解題思路：

常規思路，首先根據總長度和k值，計算得到每個分割區間的長度，然後利用pre節點得到每個區間的最後一個節點，使其指向為nullptr，遍歷完整個鏈表即可！ 遍歷完成，如果res.size()小於k值，那麼向res中添加nullptr即可，使其長度為k.

/**   * Definition for singly-linked list.   * struct ListNode {   *     int val;   *     ListNode *next;   *     ListNode(int x) : val(x), next(NULL) {}   * };   */  class Solution {  public:      vector<ListNode*> splitListToParts(ListNode* root, int k) {          int length = ;          vector<ListNode*> res;          ListNode* cur = root;          while(cur != nullptr) {              length++;              cur = cur->next;          }          int nums = length / k;          int left = length % k;          cur = root;          ListNode* pre = nullptr;          while(cur != nullptr) {              int tmp_nums = left ? nums+ : nums;              if (left > )  left -= ;    // left >= 0              res.push_back(cur);              while(tmp_nums--) {                  pre = cur;                  cur = cur->next;              }              if (pre)  pre->next = nullptr;   // 進行鏈表分割          }          int tt = k - res.size();          while(tt--)              res.push_back(nullptr);          return res;      }  };  

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/split-linked-list-in-parts

【LeetCode #168】Excel表列名稱

給定一個正整數，返回它在 Excel 表中相對應的列名稱。

例如， 1 -> A 2 -> B 3 -> C … 26 -> Z 27 -> AA 28 -> AB …

示例 1: 輸入: 1 輸出: "A"

解題思路：也就是一個26進制的問題

class Solution {  public:      string convertToTitle(int n) {          char ch = 'A';          string res = "";          while(n != ) {              n--;              res += (ch + n % );              n /= ;          }          reverse(res.begin(), res.end());          return res;      }  };  

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/excel-sheet-column-title

【LeetCode #1290】二進制鏈錶轉整數

給你一個單鏈表的引用結點 head。鏈表中每個結點的值不是 0 就是 1。已知此鏈表是一個整數數字的二進制表示形式。 請你返回該鏈表所表示數字的 十進制值 。

示例 1： 輸入：head = [1,0,1] 輸出：5 解釋：二進制數 (101) 轉化為十進制數 (5)

解題思路：

複習下鏈表反轉，首先翻轉鏈表，接着遍歷鏈表即可

class Solution {  public:      int getDecimalValue(ListNode* head) {          ListNode* pre = nullptr;          while(head != nullptr) {              ListNode* next = head->next;              head->next = pre;              pre = head;              head = next;          }          int sum = ;          int tmp = ;          while(pre != nullptr) {              sum += (pre->val * tmp);              tmp *= ;              pre = pre->next;          }          return sum;      }  };  

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/convert-binary-number-in-a-linked-list-to-integer

【LeetCode #215】數組中的第K個最大元素

在未排序的數組中找到第 k 個最大的元素。請注意，你需要找的是數組排序後的第 k 個最大的元素，而不是第 k 個不同的元素。

示例 1: 輸入: [3,2,1,5,6,4] 和 k = 2 輸出: 5

解題思路：

大根堆的創建，注意在priority_queue中建立大根堆要使用less函數（默認），小根堆使用greater函數，以及lambda表達式和priority_queue的結合使用！

class Solution {  public:      int findKthLargest(vector<int>& nums, int k) {          if(nums.size() == ) return ;          auto cmp = [](int a, int b) {              return a <= b;          };          priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);          for(auto i: nums) {              pq.push(i);          }          while((k--) > ){              pq.pop();          }          return pq.top();      }  };  

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array

【LeetCode #1019】鏈表中的下一個更大節點

給出一個以頭節點 head 作為第一個節點的鏈表。鏈表中的節點分別編號為：node_1, node_2, node_3, … 。 每個節點都可能有下一個更大值（next larger value）：對於 node_i，如果其 next_larger(node_i) 是 node_j.val，那麼就有 j > i 且 node_j.val > node_i.val，而 j 是可能的選項中最小的那個。如果不存在這樣的 j，那麼下一個更大值為 0 。 返回整數答案數組 answer，其中 answer[i] = next_larger(node_{i+1}) 。

注意：在下面的示例中，諸如 [2,1,5] 這樣的輸入（不是輸出）是鏈表的序列化表示，其頭節點的值為 2，第二個節點值為 1，第三個節點值為 5 。

示例 1： 輸入：[2,7,4,3,5] 輸出：[7,0,5,5,0]

解題思路：

構建一個單調遞減的單調棧，比如[2,7,4,3,5]，遍歷壓入棧中，當棧中元素為[2]時，滿足單調棧，遍歷到7，由於7 > 2，則不滿足，應將所有小於7的元素全部pop，這樣才能滿足單調棧，因此遍歷結束後，單調棧中只會剩餘[7, 5]，將其置零即可！

class Solution {  public:      vector<int> nextLargerNodes(ListNode* head) {          vector<int> res;          stack<int> sta;    // 構建單調棧，存放單調遞減的數值序列          int i = ;          while(head != nullptr) {              while(!sta.empty() && head->val > res[sta.top()]){                  res[sta.top()] = head->val;                  sta.pop();              }                res.push_back(head->val);              sta.push(i++);              head = head->next;          }          while(!sta.empty()) {              res[sta.top()] = ;              sta.pop();          }          return res;      }  };  

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/next-greater-node-in-linked-list

【LeetCode #503】下一個更大的元素 II

給定一個循環數組（最後一個元素的下一個元素是數組的第一個元素），輸出每個元素的下一個更大元素。數字 x 的下一個更大的元素是按數組遍歷順序，這個數字之後的第一個比它更大的數，這意味着你應該循環地搜索它的下一個更大的數。如果不存在，則輸出 -1。

示例 1: 輸入: [1,2,1] 輸出: [2,-1,2] 解釋: 第一個 1 的下一個更大的數是 2； 數字 2 找不到下一個更大的數； 第二個 1 的下一個最大的數需要循環搜索，結果也是 2。

解題思路：

這道題與上面的題是一個解法，使用單調遞減的單調棧處理，不同的是上面由於是鏈表，不支持index，需要先拷貝到res中，再進行處理。而這道題目本身就是vector，因此不再需要將數據拷貝到res中，可以直接通過索引賦值！ 本題最後一個元素是第一個元素，屬於循環數組，我們遍歷兩次就可以了！

class Solution {  public:      vector<int> nextGreaterElements(vector<int>& nums) {          int n = nums.size();          vector<int> res(n, -1);          stack<int> sta;          for(int i = ; i < n*; i++) {              while(!sta.empty() && nums[sta.top()] < nums[i % n]) {                  res[sta.top()] = nums[i % n];                  sta.pop();              }              if (i < n) {                  sta.push(i);              }          }          return res;      }  };  

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/next-greater-element-ii