题目：Container With Most Water
给定一个int数组，找到两个值，以其下标的差为宽度，最短高度为高度求面积。
思路：
定义两个指针，一个从前往后，一个从后往前；
每次固定前面的指针，后面的遍历一遍找到最大的面积(和前面的循环结果比较)记录下来。
/*************************************************************************** Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water. Note: You may not slant the container and n is at least 2. ***************************************************************************/ #include <stdio.h> int maxArea(int* height, int heightSize) { int maxi = 0,max = 0; int curh = 0,cur = 0; for(int i = 0;i < heightSize;i++){ if(height[i] <= maxi)continue;//当后续搜索的height比之前的小时，由于宽度（i->j）在减小，面积不可能比当前最优值还好，所以舍弃 maxi = height[i]; for(int j = heightSize - 1;j > i;j--){ curh = height[i] > height[j] ? height[j] : height[i]; cur = curh*(j - i); if(cur > max){ max = cur; } if(curh == height[i])break;//当当前得到的面积的高度是height[i]时，继续搜索由于宽度减小，且高度不会超过height[i]，所以放弃 } } return max; } int main(){ int h[] = {2,4,3,2,1}; int maxA = maxArea(h,5); printf("%d ",maxA); }
还有复杂度O(n)的做法。
同样定义和上面一样的指针，要求最大面积，指针移动时宽度会减小，所以要尽量找最小高度更大的，
所以每次比较两个指针的高度，最小的如果是前面的指针，则右移一位，否则后面的指针左移一位。
这样保证高度是递增的形式。
int maxArea(vector<int>& height){ int area = 0; auto head = height.begin(); auto end = height.begin(); end += height.size() - 1; while (head != end){ int temp;//记录当前面积 if ((*head) >= (*end)){ temp = (*end)*(end - head); --end; } else{ temp = (*head)*(end - head); ++head; } if (temp > area)area = temp; } return area; }
题目：Product of Array Except Self
给定一个数组，数组大小大于1，求数组除了每个位置外元素的积；
For example, given [1,2,3,4], return [24,12,8,6] = [2*3*4,1*3*4,1*2*4,1*2*3].
要求：不能用除法，且时间复杂度O(n)，空间复杂度O(1)。
思路：
正常情况，可以直接求数组所有元素的积，然后除以每个元素就能轻松求出结果，但是不能用除法；
也可以使用辅助的数组保存两两的乘积，然后再扩充乘积，也许也能求解，但是这都不符合要求。
假设数组A[] = {a1,a2,a3,a4,a5,a6}
那么结果R[] = { a2*a3*a4*a5*a6,
a1*a3*a4*a5*a6,
a1*a2*a4*a5*a6,
a1*a2*a3*a5*a6,
a1*a2*a3*a4*a6,
a1*a2*a3*a4*a5}
将上面的结果分为两部分发现前半是数组中1-5项的阶乘，后半是数组中2-6项的阶乘。
这样就能够不适用辅助数组，从头到尾，再从尾到头，遍历两次就能得到结果。
vector<int> LeetCode::productExceptSelf(vector<int>& nums){ vector<int>result(nums.size());//Pi = a0*a1*...*ai-1*ai+1*ai+2*...*an int product = 1, index = 1; result.at(0) = 1; for (size_t i = 0; i < nums.size() - 1; ++i){//Pi = a0*a1*...*ai-1,跳过第一个元素 product *= nums.at(i); result.at(index++) = product; } product = 1; index = index - 2; for (size_t i = nums.size() - 1; i > 0; --i){//Pi = an*an-1*...*ai+1，跳过最后一个元素 product *= nums.at(i); result.at(index) *= product; --index; } return result; }
题目：Trapping Rain Water
给定表示每个条的宽度为1的高度图的n个非负整数，计算下雨后能够收集的水量。
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
思路：
用栈保存有效高度的下标，遍历高度数组，当数组值大于0时，做一下比较：
- 当前高度比栈顶高度小，求出可盛水的容量，water = (i - s.top())*height[i];并将当前高度入栈
- 当前高度比栈顶高度大，求出可盛水的容量，并将栈顶元素出栈，然后接着比较当前高度和栈顶高度，直到栈空或比栈顶高度小时，当前高度入栈；
例如：height{0,0,5,0,3,4,2,7,0,6}
当遍历到3的时候，栈s{5}，3<5，求容量并将3入栈；
当遍历到4的时候，栈s{5,3}，4>3，求容量，并将3出栈，然后比较4<5，再求面积（此时高度为4 - 3），将4入栈；
int LeetCode::trap(vector<int>& height){ stack<int>s; int water = 0;//装水量 int i = 0;//height下标 while (i < height.size() && !height.at(i))++i;//找到第一个大于0的高度 s.push(i++); while (!s.empty() && i < height.size()){ while (i < height.size() && !height.at(i))++i;//找到下一个大于0的高度 if (i >= height.size())break; int pre = s.top(); if (height.at(pre) > height.at(i)){//当前高度比栈顶高度小，求出可盛水的容量，并入栈 water += (i - pre - 1)*height.at(i); s.push(i); } else{//当前高度比栈顶高度大，求出可盛水的容量，并出栈，直到栈空或比栈顶高度小时，入栈 water += (i - pre - 1)*height.at(pre); s.pop(); while (!s.empty() && height.at(s.top()) <= height.at(i)){//直到栈空或当前高度比栈顶高度小 water += (i - s.top() - 1)*(height.at(s.top()) - height.at(pre));//pre的高度入栈时已经求过 pre = s.top(); s.pop(); } if(!s.empty())water += (i - s.top() - 1)*(height.at(i) - height.at(pre));//pre的高度入栈时已经求过 s.push(i); } ++i; } return water; }