LeetCode 盛最多水的容器&爬楼梯 (day6 && day7)

算法做题方法：
题目懵逼时思考：
1. 想暴力破解的方法
2. 列举去情况由易到难
3. 泛化，找规律(找重复)

第一题：盛最多水的容器

题目描述：
暴力破解 ：
即遍历从头到尾所有情况找出最大值

int min(int a, int b) {					//寻找两根柱子中最小的那一根if(a > b) {return b;}else return a;
}
int maxArea(int* height, int heightSize){int sum, max = 0;for(int i = 0;  i < heightSize; i++) {for(int j = i + 1; j < heightSize; j++) {	//j = i + 1保证两根柱子不会相同sum = min(height[i], height[j]) * (j - i);if( sum > max) {max = sum;}}}return max;
}

分析：
优点：简单容易想到。
缺点：时间复杂度太高O(n ^ 2)

优化：方法如下：

https://leetcode-cn.com/problems/container-with-most-water/solution/sheng-zui-duo-shui-de-rong-qi-by-leetcode-solution/

方法分析：

做法：双指针，将两个指针分别指向开头和结尾并算出盛水量。比较两个开头和结尾的大小，小的往里收缩一个，大的不动并再次算出盛水量。循环往复，直到两指针相遇即为遍历完成。
浅谈做法优点：双指针分别从数组左右两边往里收缩，保证了宽度为优。而后又是比较高度，高度低的收缩，即保持高的不变，低的向里收缩。保持了高度为优。

C实现如下：

int maxArea(int* height, int heightSize){int temp ,max = 0;for(int i = 0 ,j = heightSize - 1;i < j;) {/*实现了低的向里收缩，高的不变*/int min = height[i] >= height[j] ? height[j--] :height[i++];temp = min * (j - i + 1);if(max < temp) {max = temp;}}return max;
}

第二题：爬楼梯

题目描述：

题目分析：

1. 暴力破解无法做到
2. 列举情况从易到难。
   a.当台阶为1时——1种方法
   b.当台阶为2时——2种方法
   c.当台阶为3时——3种方法
   d.当台阶为4时——5种方法
3. 泛化，找规律。(多列举几个步骤找规律)
   规律如下:
   f(1) = 1
   f(2) = 2
   f(3) = f(1) + f(2)
   f(4) = f(2) + f(3)
   …
   f(n) = f(n-2) + f(n-1)
   （斐波那契数列）
   该题只要求算出最终结果
   故题解如下：

int climbStairs(int n){int f1 = 1, f2 = 2, f3 = 3;if(n <= 2) return n;for(int i = 3; i <= n; i++) {f3 = f1 + f2;f1 = f2;f2 = f3;}return f3;
}