链表问题、单调栈-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