代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
You are given the head
of a linked list with n
nodes.
For each node in the list, find the value of the next greater node. That is, for each node, find the value of the first node that is next to it and has a strictly larger value than it.
Return an integer array answer
where answer[i]
is the value of the next greater node of the ith
node (1-indexed). If the ith
node does not have a next greater node, set answer[i] = 0
.
Example 1:
Input: head = [2,1,5] Output: [5,5,0]
Example 2:
Input: head = [2,7,4,3,5] Output: [7,0,5,5,0]
Constraints:
n
.1 <= n <= 104
1 <= Node.val <= 109
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:
nums = []
while head:
nums.append(head.val)
head = head.next
stk = []
n = len(nums)
ans = [0] * n
for i in range(n - 1, -1, -1):
while stk and stk[-1] <= nums[i]:
stk.pop()
if stk:
ans[i] = stk[-1]
stk.append(nums[i])
return ans
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public int[] nextLargerNodes(ListNode head) {
List<Integer> nums = new ArrayList<>();
for (; head != null; head = head.next) {
nums.add(head.val);
}
Deque<Integer> stk = new ArrayDeque<>();
int n = nums.size();
int[] ans = new int[n];
for (int i = n - 1; i >= 0; --i) {
while (!stk.isEmpty() && stk.peek() <= nums.get(i)) {
stk.pop();
}
if (!stk.isEmpty()) {
ans[i] = stk.peek();
}
stk.push(nums.get(i));
}
return ans;
}
}
/**
* 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:
vector<int> nextLargerNodes(ListNode* head) {
vector<int> nums;
for (; head; head = head->next) {
nums.push_back(head->val);
}
stack<int> stk;
int n = nums.size();
vector<int> ans(n);
for (int i = n - 1; ~i; --i) {
while (!stk.empty() && stk.top() <= nums[i]) {
stk.pop();
}
if (!stk.empty()) {
ans[i] = stk.top();
}
stk.push(nums[i]);
}
return ans;
}
};
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func nextLargerNodes(head *ListNode) []int {
nums := []int{}
for ; head != nil; head = head.Next {
nums = append(nums, head.Val)
}
stk := []int{}
n := len(nums)
ans := make([]int, n)
for i := n - 1; i >= 0; i-- {
for len(stk) > 0 && stk[len(stk)-1] <= nums[i] {
stk = stk[:len(stk)-1]
}
if len(stk) > 0 {
ans[i] = stk[len(stk)-1]
}
stk = append(stk, nums[i])
}
return ans
}
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function nextLargerNodes(head: ListNode | null): number[] {
const nums: number[] = [];
while (head) {
nums.push(head.val);
head = head.next;
}
const stk: number[] = [];
const n = nums.length;
const ans: number[] = new Array(n).fill(0);
for (let i = n - 1; ~i; --i) {
while (stk.length && stk[stk.length - 1] <= nums[i]) {
stk.pop();
}
ans[i] = stk.length ? stk[stk.length - 1] : 0;
stk.push(nums[i]);
}
return ans;
}
// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
struct Item {
index: usize,
val: i32,
}
impl Solution {
pub fn next_larger_nodes(head: Option<Box<ListNode>>) -> Vec<i32> {
let mut res = Vec::new();
let mut stack: Vec<Item> = Vec::new();
let mut cur = &head;
for i in 0..usize::MAX {
if cur.is_none() {
break;
}
res.push(0);
let node = cur.as_ref().unwrap();
while !stack.is_empty() && stack.last().unwrap().val < node.val {
res[stack.pop().unwrap().index] = node.val;
}
stack.push(Item {
index: i,
val: node.val,
});
cur = &node.next;
}
res
}
}
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {number[]}
*/
var nextLargerNodes = function (head) {
const nums = [];
while (head) {
nums.push(head.val);
head = head.next;
}
const stk = [];
const n = nums.length;
const ans = new Array(n).fill(0);
for (let i = n - 1; i >= 0; --i) {
while (stk.length && stk[stk.length - 1] <= nums[i]) {
stk.pop();
}
ans[i] = stk.length ? stk[stk.length - 1] : 0;
stk.push(nums[i]);
}
return ans;
};
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
interface Item {
index: number;
val: number;
}
function nextLargerNodes(head: ListNode | null): number[] {
const res: number[] = [];
const stack: Item[] = [];
let cur = head;
for (let i = 0; cur != null; i++) {
res.push(0);
const { val, next } = cur;
while (stack.length !== 0 && stack[stack.length - 1].val < val) {
res[stack.pop().index] = val;
}
stack.push({
val,
index: i,
});
cur = next;
}
return res;
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。