Neovim-如何使用编辑器的神

双指针算法

• 首先, 对于任意选取的两个竖线, 它们之间的面积是$min\{h(i), h(j)\} \times (j - i)$

• 选取两个指针i和j分别指向数组的开始和结尾, 每次先计算两个指针所在竖线的面积, 并维护最大值.

  • 如果$h(i) < h(j)$, 那么i向前移动.
  • 如果$h(i) > h(j)$, 那么j向后移动.
  • 相等的话移动哪边都可以, 默认移动i.

• 证明:

  • 假设最优解所在的两条竖线的下标分别是$p, q$, 指针$i, j$一定有一个会先到达最优解的边界, 不妨设$i$先到$p$, 需要证明, 按照上述算法, $j$一定会到$q$.
  • 反证: 假设$h(p) \leqslant h(j)$, 那么此时$i$指针在$p$, 它会向右移动, 但是如果要枚举到最优解, $j$指针需要向左移动.
  • 最优解的面积是$min\{h(p), h(q)\} \times (q - p)$
  • 考虑这个面积: $min\{h(p), h(j)\} \times (j - p)$, 其中$h(i) = h(p)$, 由于$h(i) = h(p) \leqslant h(j)$, 那么这个面积实际上是$h(j) \times (j - p)$
  • 但是, $min\{h(p), h(q)\} \times (q - p) < h(j) \times (j - p)$, 因此, 最优解就变成了$h(j) \times (j - p)$, 不符合原来的假设.
  • 因此, 原来的算法一定会枚举到最优解.

#include <iostream>

using namespace std;

const int N = 100010;

int n;
int h[N];

int main() {

    cin >> n;
    for (int i = 0; i < n; i ++) cin >> h[i];

    int i = 0, j = n - 1, res = -1;

    while (i < j) {
        res = max(res, min(h[i], h[j]) * (j - i));
        if (h[i] <= h[j]) i ++;
        else j --;
    }
    cout << res << endl;

    return 0;
}