31. Next Greater Element with Position Offset

Origin: Next Greater Element with Position Offset

Given an integer array readings, return an array result where result[i] = [value, distance], with value being the next greater element to the right of readings[i] and distance being the index difference. If no greater element exists, return [-1, -1].

Example

Input: readings = [2, 1, 2, 4, 3]

Output: [[4, 3], [2, 1], [4, 1], [-1, -1], [-1, -1]]

Explanation:

• i=0, value=2，右边第一个比 2 大的是 4，在索引 3，距离 3-0=3 → [4, 3]
• i=1, value=1，右边第一个比 1 大的是 2，在索引 2，距离 2-1=1 → [2, 1]
• i=2, value=2，右边第一个比 2 大的是 4，在索引 3，距离 3-2=1 → [4, 1]
• i=3, value=4，右边没有更大的 → [-1, -1]
• i=4, value=3，右边没有更大的 → [-1, -1]

Input Format

• 第一行：n（数组长度）
• 接下来 n 行：每行一个数组元素

Constraints

• 0 <= readings.length <= 100000
• -10^9 <= readings[i] <= 10

Output Format

返回 n 个 [value, distance] 对。不存在返回 [-1, -1]。

Sample Input 0

1
5

Sample Output 0

-1 -1

Sample Input 1

5
2 1 2 4 3

Sample Output 1

4 3 2 1 4 1 -1 -1 -1 -1

---

函数契约

// 输入：readings（整数数组）
// 输出：[[value, distance], ...] 每个元素的下一个更大元素及其索引距离
// 边界：空数组 → []；单元素 → [[-1, -1]]；最后一个元素 → [-1, -1]

边界表

场景	返回什么
空数组	[]
单元素	-1, -1
递增数组	每个都指向下一个
递减数组	全部 [-1, -1]
正常场景	[nextGreaterValue, distance]

Resolution

我的解法（单调栈，O(n) AC）

function findNextGreaterElementsWithDistance(readings: number[]): number[][] {
    const stack: number[] = []
    const result = Array.from({ length: readings.length }, () => [-1, -1])
    for (let i = readings.length - 1; i >= 0; i--) {
        const cur = readings[i]
        while (stack.length > 0 && cur >= readings[stack[stack.length - 1]]) {
            stack.pop()
        }
        if (stack.length > 0) {
            const index = stack[stack.length - 1]
            result[i] = [readings[index], index - i]
        }
        stack.push(i)
    }
    return result
}

暴力解法（O(n²)，也能 AC）

function findNextGreaterElementsWithDistance(readings: number[]): number[][] {
    let result: number[][] = []
    for (let i = 0; i < readings.length; i++) {
        for (let j = i + 1; j <= readings.length; j++) {
            if (j > readings.length - 1) {
                result.push([-1, -1])
                break
            }
            if (readings[j] > readings[i]) {
                result.push([readings[j], j - i])
                break
            }
        }
    }
    return result
}

解题思路

单调栈：从右往左遍历，维护一个从底到顶递减的栈（存索引）。

每个元素做三件事：

1. 弹出：栈顶比当前值小的全部弹出，它们被当前值挡住了，对左边的元素没用了
2. 读取：栈顶如果还有元素，那就是右边第一个更大的，算出距离
3. 入栈：当前索引入栈

为什么是 O(n)？ 每个元素最多入栈一次、出栈一次，总共最多 2n 次操作。

为什么用单调栈？ 暴力解对每个元素往右扫找更大的，O(n²)。但如果右边有比它小的，那些小元素对它左边的元素也没用（被它挡住了）。单调栈帮你跳过这些没用的元素，只保留”可能成为答案”的候选。

两解对比

	暴力解	单调栈
思路	每个元素往右扫	从右往左，栈维护候选
时间	O(n²)	O(n)
空间	O(1)	O(n)，栈

复杂度

• 时间：O(n)，每个元素入栈出栈各一次
• 空间：O(n)，栈最多存 n 个索引

参考来源

• 相关文章：算法解题流程：从读题到提交的七步