字节跳动面试题
题目描述
给定一个数组a，找出a[i] - a[j]的最大值，且满足i > j
要求
时间复杂度为O(n)，空间复杂度为O(1)
样例
输入：

6
50 9 30 2 10 31

输出：

29

说明
这道题慢指针j不是一步步往后走的（j ++），而是当满足条件时一次性跳到i的位置(j = i)

题解
这是我在字节跳动夏令营面试时遇到的题目，拿到题目首先想到要用双指针算法，但可能因为紧张，一下子没想出怎么做，后来发现双指针好像空间复杂度不满足要求，于是直接维护min
虽然双指针不满足要求，但也提供了一种指针变化的情况

• （暴力）O(n^2) 比较简单，但会超时

    // 暴力做法 时间复杂度o(n^2)
    int res = -0x3f3f3f3f;
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j < i; j ++) {
            res = max(res, a[i] - a[j]);
        }
    }

• （双指针算法）时间复杂度为O(n)，空间复杂度为O(n)
  考虑当a[j] > a[i]时，那后面在计算最大值时一定与a[j]无关，因为a[i]比a[j]更小，可替换a[j]

C++代码

#include <iostream>

using namespace std;

const int N = 1010;

int a[N];

int main() {
    int n;
    cin >> n;

    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
    }

    // 算法核心
    int res = -0x3f3f3f3f;
    for (int i = 2, j = 1; i <= n; i ++) { // i先动，j后动
        if (a[i] <= a[j]) {
            j = i;  // 一次性跳到i
        } else {
            res = max(res, a[i] - a[j]);
        }
    }

    // 特殊处理
    if (res == -0x3f3f3f3f) {
        for (int i = 2; i <= n; i ++) {
            res = max(res, a[i] - a[i - 1]);
        }
    }

    cout << res << endl;

    return 0;
}

• （维护min） 时间复杂度为O(n)，空间复杂度为O(1)

#include <iostream>

using namespace std;

const int N = 1010;

int a[N];

int main() {
    int n, x, res = -0x3f3f3f3f, mi = 0x3f3f3f3f;
    cin >> n;

    for (int i = 1; i <= n; i ++) {
        cin >> x;
        res = max(res, x - mi);
        mi = min(x, mi);
    }

    cout << res << endl;

    return 0;
}

和83.股票的最大价值类似

class Solution {
public:
    int maxDiff(vector<int>& nums) {
        if (nums.size() <= 1) return 0;
        int idx = 0;
        int d = -0x3f3f3f3f;
        for (int i = 1; i < nums.size(); i ++) {
            d = max(d, nums[i] - nums[idx]);
            if (nums[i] <= nums[idx]) idx = i;
        }
        if (d < 0) return 0;
        return d;
    }
};