今天有时间参加了一下Leetcode Weekly Contest 116，参加的比较晚，完成两题之后没时间做其他的了，在这里写一下完成的两题中的一题。题目如下：

Given an array A of integers, a ramp is a tuple (i, j) for which i < j and A[i] <= A[j]. The width of such a ramp is j - i. Find the maximum width of a ramp in A. If one doesn’t exist, return 0.

题目意思是这样，给定一个数组A，将符合如下条件数字对(i, j)定义为ramp：

  1. i, j 是数组A中的下标
  2. A[i] <= A[j]

并定义ramp的距离是j - i，求数组中最大的ramp距离，如果不存在则返回 0。

这题思路其实很简单，直接遍历即可。对于每一个固定的下标i，从数组的右边开始遍历，直到找到一个比A[i]大的数字A[j]即可，同时记录距离j - i。另外，如果最大距离已经超过了下标i可能的最大距离，也即n - 1 - i，则直接退出循环，因为这个时候不可能找到比当前距离更大的数字了。

举例：给定数组[6,0,8,2,1,5]，当i = 2时，之前记录的最大距离是5 - 1（i = 1的时候），而i >=2的情况下，可能出现的最大ramp也不会超过4，所以这个时候可以直接退出循环，4即为最大ramp距离。

具体实现的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int maxWidthRamp(int[] A) {
        int n = A.length;
        int max = 0;
        for (int i = 0; i < n; i ++) {
            if(max >= n - 1 - i){
                break;
            }
            for (int j = n - 1; j > i; j --) {
                if (A[j] >= A[i]) {
                    max = Math.max(max, j - i);
                }
            }
        }
        return max;
    }
}

这种思路的最差时间复杂度是O(n^2)，最优时间复杂度是O(1)，空间复杂度是O(1)。