近期在做题的时候，有两道题目比较有启发。

题目来源：LeetCode

：给定 n 个非负整数 a₁，a_2，...，a_n，每个数代表坐标中的一个点 (i, a_i) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, a_i) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

在做“盛水最多的容器”时，最开始的想法是动态规划，寻找转移方程。但是思索了很久没有想到后一个状态与前一个状态的联系。后来看了解析之后，发现了一种新的看待问题和寻找最优解的思路。

在做这题时，使用双指针，一个指向最左，一个指向最右，维护一个当前的最大值。

思路重点：将两个指针中较小的那一个往中间移动。

背后原理：当前已经有了一个最大值了，可以看做是当前信息条件下的最优。而能够优化这个问题的办法就是将限制当前值的条件进行改变，尝试寻找更优的解法。即，将较小的指针往中间移动。

在其他问题中，也可以通过这种方式寻找思路：找到一个部分最优解，通过优化当前的短板，进而优化整个问题。

class Solution {    public int getArea(int[] height, int start, int end)    {        return Math.min(height[start], height[end])*(end-start);    }    public int maxArea(int[] height) {        int n = height.length;        int start = 0, end = n-1;        int max_area = 0;        while (start!=end)        {            int temp_area = getArea(height, start, end);            max_area = Math.max(max_area, temp_area);            if (height[start] > height[end])                end--;            else                start++;        }        return max_area;    }}

 

接雨水问题相对更加复杂。最一开始我的想法整个是错误的：从左向右找“坑”，然后找到一个坑就计算这个坑能接多少，最后加起来。但是这种想法的问题在于没有想到可能有更大的坑包住了这些小坑，根本原因在于局部小坑的边界可能并不是盛水的边界，而可能被包着它的更大的坑漫过。

而这个问题实际的想法是：找到所有柱子里的最大值。这样，最大值这个柱子就不可能被其他的更大的坑漫过。由此，分为了左右两个部分，从左和从右分别向最大值靠近即可。

class Solution {        public int trap(int[] height) {        if (height == null || height.length <3)            return 0;        int pos=0, highest = 0, n = height.length;        for (int i = 0; i < n; ++i)        {            if (height[i] > highest)            {                highest = height[i];                pos = i;            }        }        int temp = height[0], result = 0;        for (int i = 0; i < pos; ++i)        {            if (height[i] < temp)                result += (temp - height[i]);            else                temp = height[i];        }        temp = height[n-1];        for (int i = n-1; i >= pos; --i)        {            if (height[i] < temp)                result += (temp-height[i]);            else                temp = height[i];        }        return result;    }}

而另一个更近一步的做法是结合前一题的想法，不用第一次先遍历找到最大值，再左右向中间靠近。而可以左右两个指针，谁小向中间移动谁。这样做实际上相当于在这一次遍历的过程中，既找了最大值，又计算了水量。

class Solution {public:    int trap(vector
     
      & height) {        int result = 0;        for (int i = 0, j = height.size() - 1, left_max = 0, right_max = 0; i < j; )        {            if (height[i] > left_max) left_max = height[i];            if (height[j] > right_max) right_max = height[j];            if (left_max <= right_max) result += left_max - height[i++];            else result += right_max - height[j--];        }        return result;    }};