链表中的下一个更大节点

1019. 链表中的下一个更大节点

给定一个长度为 n 的链表 head

对于列表中的每个节点，查找下一个 更大节点 的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值 严格大于 它的值。

返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点，设置 answer[i] = 0 。

示例 1：

输入：head = [2,1,5]
输出：[5,5,0]

示例 2：

输入：head = [2,7,4,3,5]
输出：[7,0,5,5,0]

提示：

链表中节点数为 n
1 <= n <= 10⁴
1 <= Node.val <= 10⁹

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

/** * 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) { } };

python3 解法, 执行用时: 200 ms, 内存消耗: 19.3 MB, 提交时间: 2022-12-04 13:48:14

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def nextLargerNodes(self, head: ListNode) -> List[int]:
        # 转为顺序表
        cur = head
        nums = []
        while cur:
            nums.append(cur.val)
            cur = cur.next
        
        # 求解
        stack = []
        result = [0 for i in range(len(nums))]
        for j in range(len(result)-1, -1, -1):
            if not stack:
                stack.append(nums[j])
                continue
            else:
                x  = nums[j]
                while stack and stack[-1] <= x:
                    stack.pop()
                if stack:
                   result[j] = stack[-1]
                stack.append(x)
        
        return result

python3 解法, 执行用时: 188 ms, 内存消耗: 19.6 MB, 提交时间: 2022-12-04 13:47:35

# 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: ListNode) -> List[int]:        
        nums = []
        node = head
        while node != None :
            nums.append(node.val)
            node = node.next

        stack = []
        stack_loc = []
        res = [0] * len(nums)

        for i in range(len(nums)):
            while stack and stack[-1] < nums[i]:
                res[stack_loc[-1]] = nums[i]
                stack.pop()
                stack_loc.pop()
            stack.append(nums[i])
            stack_loc.append(i)

        return res

python3 解法, 执行用时: 224 ms, 内存消耗: 20.4 MB, 提交时间: 2022-12-04 13:46:50

# 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: ListNode) -> List[int]:
        res = []
        st = []
        cur = head
        while cur:
            res.append(0)
            cur_idx = len(res) - 1
            while len(st) > 0 and cur.val > st[-1][0].val:
                node, idx = st.pop()
                res[idx] = cur.val
            st.append((cur, cur_idx))
            cur = cur.next
        return res

java 解法, 执行用时: 53 ms, 内存消耗: 45.4 MB, 提交时间: 2022-12-04 13:46:31

/**
 * 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 {
    int[] res;
    
    public int[] nextLargerNodes(ListNode head) {
        calNode(head, 0, new Stack<>());
        return res;
    }
    
    public void calNode(ListNode node, int index, Stack<Integer> stack) {
        if (node == null) {
            res = new int[index];//初始化数组的大小
            return;
        }
        calNode(node.next, index + 1, stack);
        while (!stack.empty() && stack.peek() <= node.val)
            stack.pop();
        res[index] = stack.empty() ? 0 : stack.peek();
        stack.push(node.val);
    }
}

java 解法, 执行用时: 40 ms, 内存消耗: 44.3 MB, 提交时间: 2022-12-04 13:45:59

/**
 * 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> list = new ArrayList<>();
        Stack<Integer> stack = new Stack();
        for (ListNode node = head; node != null; node = node.next) {
            while (!stack.isEmpty() && node.val > list.get(stack.peek())) {
                list.set(stack.pop(), node.val);
            }
            stack.push(list.size());
            list.add(node.val);
        }
        for (int i : stack) {
            list.set(i, 0);
        }
        int[] res = new int[list.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = list.get(i);
        }
        return res;
    }
}

java 解法, 执行用时: 7 ms, 内存消耗: 45.5 MB, 提交时间: 2022-12-04 13:45:37

/**
 * 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> list = new ArrayList<>();
        //链表元素存储到集合中
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        int[] res = new int[list.size()];
        for (int i = res.length - 1; i >= 0; i--) {
            int j = i + 1;
            int num = 0;
            if (j < res.length)
                num = list.get(j);
            while (j < res.length) {
                if (num > list.get(i)) {
                    //如果找到就停止while循环
                    res[i] = num;
                    break;
                } else if (num == 0) {
                    break;
                } else {
                    num = res[j++];
                }
            }
        }
        return res;
    }
}

java 解法, 执行用时: 39 ms, 内存消耗: 44.8 MB, 提交时间: 2022-12-04 13:45:19

/**
 * 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> list = new ArrayList<>();
        //链表元素存储到集合中
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        //栈中存储的是元素的下标，并且从栈底到栈顶元素在集合中对应的
        //值是从大到小的
        Stack<Integer> stack = new Stack<>();
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            while (!stack.empty() && list.get(stack.peek()) < list.get(i)) {
                //如果栈顶元素对应的值小于当前值，说明栈顶元素遇到了比他小的
                int index = stack.pop();
                res[index] = list.get(i);
            }
            stack.push(i);
        }
        return res;
    }
}

java 解法, 执行用时: 1361 ms, 内存消耗: 45.1 MB, 提交时间: 2022-12-04 13:45:02

/**
 * 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> list = new ArrayList<>();
        //链表元素存储到集合中
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size() - 1; i++) {
            for (int j = i + 1; j < list.size(); j++) {
                if(list.get(j)>list.get(i)){
                    res[i]=list.get(j);
                    break;
                }
            }
        }
        return res;
    }
}

上一题

下一题

详情