題目

如果連續(xù)數(shù)字之間的差嚴(yán)格地在正數(shù)和負(fù)數(shù)之間交替，則數(shù)字序列稱(chēng)為擺動(dòng)序列。第一個(gè)差（如果存在的話(huà)）可能是正數(shù)或負(fù)數(shù)。少于兩個(gè)元素的序列也是擺動(dòng)序列。

例如， [1,7,4,9,2,5] 是一個(gè)擺動(dòng)序列，因?yàn)椴钪?(6,-3,5,-7,3) 是正負(fù)交替出現(xiàn)的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是擺動(dòng)序列，第一個(gè)序列是因?yàn)樗那皟蓚€(gè)差值都是正數(shù)，第二個(gè)序列是因?yàn)樗淖詈笠粋€(gè)差值為零。

給定一個(gè)整數(shù)序列，返回作為擺動(dòng)序列的最長(zhǎng)子序列的長(zhǎng)度。 通過(guò)從原始序列中刪除一些（也可以不刪除）元素來(lái)獲得子序列，剩下的元素保持其原始順序。

示例 1:輸入: [1,7,4,9,2,5] 輸出: 6 解釋: 整個(gè)序列均為擺動(dòng)序列。 示例 2:輸入: [1,17,5,10,13,15,10,5,16,8] 輸出: 7 解釋: 這個(gè)序列包含幾個(gè)長(zhǎng)度為 7 擺動(dòng)序列，其中一個(gè)可為[1,17,10,13,10,16,8]。 示例 3:輸入: [1,2,3,4,5,6,7,8,9] 輸出: 2

題目的意思大概就是這段數(shù)組必須是起伏的。大概就是比如數(shù)組a[0]>a[1]那么a[1]<a[2],a[2]>a[3]

大概就是這樣。
然后我們一段數(shù)列就是如果不是搖擺序列我們就找他的最大子序列，如果不是搖擺序列就代表著他是有一段遞增或者是遞減的序列。如圖所示

這段數(shù)組中 a[1]-a[5]以及a[8]-a[10]都是遞減的，a[5]-a[8]是遞增的這明顯不是擺動(dòng)序列，所以我們可以找他的最大擺動(dòng)子序列。按照貪心的原則我們肯定在遞減序列中找最小的，在遞增序列中找最大的，這樣在轉(zhuǎn)折點(diǎn)就是可以與下一個(gè)數(shù)字組成搖擺序列。比如該圖中，我們肯定選取轉(zhuǎn)折點(diǎn)。

現(xiàn)在我們來(lái)看看代碼

class Solution {public int wiggleMaxLength(int[] nums) {if(nums.length<2){return nums.length;}/**總共有兩種狀態(tài) 上升和下降。我們需要的擺動(dòng)序列就是上升和下降這兩種狀態(tài)交替進(jìn)行。**/final int up=1;/**switch中 case中使用的必須是常量 使用變量需要用final修飾**/final int down=2;final int start=0;int a=start;int maxlength=1;//最大擺動(dòng)序列初始為1for(int i=1;i<nums.length;i++){switch(a){case start:if(nums[i-1]<nums[i]){a=up;maxlength++;}else if(nums[i-1]>nums[i]){a=down;maxlength++;}break;case up:if(nums[i-1]>nums[i]){a=down;maxlength++;}break;case down:if(nums[i-1]<nums[i]){a=up;maxlength++;}break;}}return maxlength;} }

在搖擺序列中，有兩種狀態(tài)向上(遞增)或者向下(遞減)，我們分別用up和down表示。我們需要知道第一個(gè)狀態(tài)是什么所以設(shè)置了一個(gè)start，一開(kāi)始switch里的變量就是start，然后通過(guò)case start中的代碼nums[i]與nums[i-1]的大小來(lái)判斷當(dāng)前的狀態(tài)然后讓switch的下一個(gè)去尋找該狀態(tài)的代碼，總體的思路大致是這樣。今天也是我正式的去了解貪心算法所以記錄一下自己的思路。在做這道題目的時(shí)候我也卡了一下，原因是在于switch中case中使用的必須是常量（java中得在變量前使用final表示），而我忘記了這個(gè)基礎(chǔ)語(yǔ)法知識(shí)一直卡在編譯那邊，通過(guò)這道題目更加的發(fā)現(xiàn)自己的無(wú)知與粗細(xì)。

總結(jié)

以上是生活随笔為你收集整理的贪心---leetcode-376摆动序列的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。