链表问题、单调栈-LeetCode 430、725、168、1290、215、1019、503（递减型单调栈）
链表问题、单调栈-LeetCode 430、725、168、1290、215、1019、503（递减型单调栈）
作者：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