滑动窗口，最长子序列最好的选择 -＞ O(N)

最近在学校上短学期课程，做程序设计题，一下子回忆起了大一学数据结构与算法的日子！

这十天我会记录一些做题的心得，今天带来的是对于最长子序列长度题型的解题框架：滑动窗口

本质就是双指针算法：

通过left和right指针构建一个左闭右开的窗口window：（left, right]

首先，通过right指针向右expand窗口

窗口满足题设条件的话就一直expand，直到条件被打破。

此时窗口不满足题设条件，需要通过left指针向右shrink窗口，直到再次满足题设条件。

题目变化，变的就是如何maintain这个窗口而已。

k

int fun(int* A, int N,int S) {
//	sliding window// The window we maintain is like [left, right)int left = 0, right = 0;int windowSum = 0;int Max = 0;while(right < N) {// right expandingwindowSum += A[right++];Max = windowSum <= S && right - left > Max ? right - left : Max;// shrinkingwhile(left <= right && windowSum > S) {windowSum -= A[left++];}}return Max;
}

int fun(int* A, int N,int S) {
//	sliding window// The window we maintain is like [left, right)int left = 0, right = 0;int Max = 0;// maintain the local minimum and local maximumint winMin = A[0];int winMax = A[0];while(right < N) {// right expandingif(A[right] > winMax) {winMax = A[right];}else if(A[right] < winMin) {winMin = A[right];}right++;Max = winMax - winMin <= S && right - left > Max ? right - left : Max;// shrinkingwhile(left <= right && winMax - winMin > S) {
//			Don't forget to initialize the local value before setting.left++;winMin = A[left];winMax = A[right];
//			set the maximum and minimum in the new windowfor(int i = left; i < right; i++) {if(A[i] > winMax) {winMax = A[i];}else if(A[i] < winMin) {winMin = A[i];}}}}return Max;
}