376. Wiggle Subsequence

題目理解

給定一個數組，相鄰兩個數計算差值。差值排成的序列是正負相間的，那這個數組就是一個wiggle 數組。例如數組[1,7,4,9,2,5]，差值序列是(6,-3,5,-7,3)。原數組用坐標軸表示如下。

思路是：在一段連續上升或者連續下降的線段上，那只保留兩端的斷點（這是貪心思想的體現），去掉中間的斷點，就能使得子序列符合要求。例如在AB線段上，去掉中間點A1,A2A1,A2，在BC線段上去掉B1,B2B1,B2，那留下在子序列[A,B,C]就是符合要求的，并且是長度最長的wiggle子序列。
證明：要證明上面的思路是正確的。可以使用反證法。假如在一段連續上升的線段中不是保留最頂點B，而是留下A2A2點，刪除一個點，添加一個點，總長度不發生變化。那會影響其他點嗎？A2<BA2<B。B點之后是一段下降的線段。<A2<A2<script type="math/tex" id="MathJax-Element-879"><B<B<script type="math/tex" id="MathJax-Element-880"><B<B<script type="math/tex" id="MathJax-Element-881"><A2<A2<script type="math/tex" id="MathJax-Element-882">A2A2替換B沒有任何好處。可以用同理分析下降線段中去掉中間點是最合理的。
學習：對于每一種解決方法是應該有證明的。此外，本題目還要考慮各種變化趨勢，增加測試數據。
考慮：先直線再折線；先折線再直線；折線折線直線；折線直線折線。

public int wiggleMaxLength(int[] nums) {if(nums.length<=1){return nums.length;}int ans = 1;int diff = nums[1]-nums[0];if(diff!=0){ans++;}for(int i=2;i<nums.length;i++){if(nums[i]!=nums[i-1]){if(diff * (nums[i]-nums[i-1])<=0){ans++;}diff = nums[i]-nums[i-1];}}return ans;}

總結

以上是生活随笔為你收集整理的376 Wiggle Subsequence 贪心解法以及证明的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。