golang 解法, 执行用时: 52 ms, 内存消耗: 6.6 MB, 提交时间: 2023-09-19 14:49:42

/**
 * 先按照索引排序，排序后的索引数组保证[i,j]上nums[index[j]] >= nums[index[i]]
 * 然后遍历索引数组更新最大差值和前缀最小索引值
 */
func maxWidthRamp(nums []int) int {
    n := len(nums)
    index := make([]int, n)
    for i := range index {
        index[i] = i
    }
    sort.Slice(index, func(i, j int) bool {
        return nums[index[i]] < nums[index[j]] || nums[index[i]] == nums[index[j]] && index[i] < index[j] 
    })
    minIndex := n
    ans := 0
    for _, v := range index {
        if v - minIndex > ans {
            ans = v - minIndex
        }
        if v < minIndex {
            minIndex = v
        }
    }
    return ans
}

golang 解法, 执行用时: 44 ms, 内存消耗: 8.5 MB, 提交时间: 2023-09-19 14:47:07

func maxWidthRamp(nums []int) int {
    var order [][]int
    order = append(order, []int{0, nums[0]})
    //构建递减序列
    for i := 1; i < len(nums); i++ {
        if nums[i] < order[len(order)-1][1] {
            order = append(order, []int{i, nums[i]})
        }
    }
    res := 0
    for j, target := range nums {
        i := binarySearch(order, target)
        res = max(res, j-i)
    }
    return res
}

//找第一个小于等于target的值
func binarySearch(num [][]int, target int) int {
    left := 0
    right := len(num) - 1
    for left < right {
        mid := left + (right-left)/2
        if num[mid][1] > target {
            left = mid + 1 //注意是递减序列
        } else {
            right = mid
        }
    }
    return num[left][0]
}

func max(a, b int) int { if a > b { return a }; return b }

python3 解法, 执行用时: 76 ms, 内存消耗: 21.5 MB, 提交时间: 2023-09-19 14:42:14

'''
方法三：单调栈
'''
class Solution:
    def maxWidthRamp(self, nums: List[int]) -> int:
        ans = 0
        n = len(nums)
        stack = []
        # 单调递减栈,维护一个下坡,因为i < j 且 A[i] <= A[j]
        # 所以我们选择比stack[-1]更小的元素进行保存
        # 如果更大或相等,显然stack[-1]更优,因为其在num的左边
        for i, num in enumerate(nums):
            if not stack or nums[stack[-1]] > num:
                stack.append(i)
        
        # 从后向前遍历,如果栈顶值小于或等于当前值,则计算宽度
        # 为什么可以删除栈顶值?
        # 因为我们从后向前遍历,如果还有大于栈顶的值,那其一定在当前值的左边
        # 但右边的宽度更大,所以可以删除
        for i in range(n-1,-1,-1):
            if i < ans: break
            while stack and nums[stack[-1]] <= nums[i]:
                ans = max(ans,i-stack.pop())
        return ans

python3 解法, 执行用时: 152 ms, 内存消耗: 23.2 MB, 提交时间: 2023-09-19 14:36:32

'''
方法二：二分检索候选位置
按照降序考虑 i ， 我们希望找到一个最大的 j 满足 A[j] >= A[i]（如果存在的话）。
因此，候选的 j 应该是降序的：如果存在 j1 < j2 并且 A[j1] <= A[j2] ，那么我们一定会选择 j2。
'''
class Solution:
    def maxWidthRamp(self, nums: List[int]) -> int:
        n = len(nums)

        ans = 0
        candidates = [(nums[n-1], n-1)]
        # candidates: i's decreasing, by increasing value of A[i]
        for i in range(n-2, -1, -1):
            # Find largest j in candidates with A[j] >= A[i]
            jx = bisect.bisect(candidates, (nums[i],))
            if jx < len(candidates):
                ans = max(ans, candidates[jx][1] - i)
            else:
                candidates.append((nums[i], i))

        return ans

java 解法, 执行用时: 15 ms, 内存消耗: 49.5 MB, 提交时间: 2023-09-19 14:34:21

// 二分检索位置
import java.awt.Point;

class Solution {
    public int maxWidthRamp(int[] A) {
        int N = A.length;

        int ans = 0;
        List<Point> candidates = new ArrayList();
        candidates.add(new Point(A[N-1], N-1));

        // candidates: i's decreasing, by increasing value of A[i]
        for (int i = N-2; i >= 0; --i) {
            // Find largest j in candidates with A[j] >= A[i]
            int lo = 0, hi = candidates.size();
            while (lo < hi) {
                int mi = lo + (hi - lo) / 2;
                if (candidates.get(mi).x < A[i])
                    lo = mi + 1;
                else
                    hi = mi;
            }

            if (lo < candidates.size()) {
                int j = candidates.get(lo).y;
                ans = Math.max(ans, j - i);
            } else {
                candidates.add(new Point(A[i], i));
            }
        }
        return ans;
    }
}

java 解法, 执行用时: 56 ms, 内存消耗: 52.3 MB, 提交时间: 2023-09-19 14:33:56

class Solution {
    public int maxWidthRamp(int[] A) {
        int N = A.length;
        Integer[] B = new Integer[N];
        for (int i = 0; i < N; ++i)
            B[i] = i;

        Arrays.sort(B, (i, j) -> ((Integer) A[i]).compareTo(A[j]));

        int ans = 0;
        int m = N;
        for (int i: B) {
            ans = Math.max(ans, i - m);
            m = Math.min(m, i);
        }

        return ans;
    }
}

python3 解法, 执行用时: 104 ms, 内存消耗: 22.9 MB, 提交时间: 2023-09-19 14:33:21

'''
方法一：排序
对于每一个形如 nums[i] = v 的元素，我们将其索引 i 按照对应值 v 排序之后的顺序写下。
例如， A[0] = 7, A[1] = 2, A[2] = 5, A[3] = 4，我们应该这样顺序写下索引值 i=1, i=3, i=2, i=0。

然后，当我们写下一个索引 i 的时候，我们可以得到候选的宽度答案
i - min(indexes_previously_written) （如果这个值是正数的话）。 
我们可以用一个变量 m 记录已经写下的最小索引。
'''
class Solution:
    def maxWidthRamp(self, nums: List[int]) -> int:
        ans = 0
        m = float('inf')
        for i in sorted(range(len(nums)), key = nums.__getitem__):
            ans = max(ans, i - m)
            m = min(m, i)
        return ans