日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

添加新題啦，本題是一道雙指針的經(jīng)典應(yīng)用，感受一下吧!

有效的山脈數(shù)組力扣題目鏈接：https://leetcode-cn.com/problems/valid-mountain-array/

給定一個(gè)整數(shù)數(shù)組 arr，如果它是有效的山脈數(shù)組就返回 true，否則返回 false。

讓我們回顧一下，如果 A 滿(mǎn)足下述條件，那么它是一個(gè)山脈數(shù)組：

arr.length >= 3

在 0 < i < arr.length - 1 條件下，存在 i 使得：

• arr[0] < arr[1] < ... arr[i-1] < arr[i]
• arr[i] > arr[i+1] > ... > arr[arr.length - 1]

示例 1：

• 輸入：arr = [2,1]
• 輸出：false

示例 2：

• 輸入：arr = [3,5,5]
• 輸出：false

示例 3：

• 輸入：arr = [0,3,2,1]
• 輸出：true

思路

判斷是山峰，主要就是要嚴(yán)格的保存左邊到中間，和右邊到中間是遞增的。

這樣可以使用兩個(gè)指針，left和right，讓其按照如下規(guī)則移動(dòng)，如圖：

注意這里還是有一些細(xì)節(jié)，例如如下兩點(diǎn)：

• 因?yàn)閘eft和right是數(shù)組下表，移動(dòng)的過(guò)程中注意不要數(shù)組越界
• 如果left或者right沒(méi)有移動(dòng)，說(shuō)明是一個(gè)單調(diào)遞增或者遞減的數(shù)組，依然不是山峰

C++代碼如下：

 
 
 
 

  
  
  
  
class Solution { 
  
  
  
  
public: 
  
  
  
  
    bool validMountainArray(vector& A) { 
  
  
  
  
        if (A.size() < 3) return false; 
  
  
  
  
        int left = 0; 
  
  
  
  
        int right = A.size() - 1; 
  
  
  
  
 
  
  
  
  
        // 注意防止越界 
  
  
  
  
        while (left < A.size() - 1 && A[left] < A[left + 1]) left++; 
  
  
  
  
 
  
  
  
  
        // 注意防止越界 
  
  
  
  
        while (right > 0 && A[right] < A[right - 1]) right--; 
  
  
  
  
 
  
  
  
  
        // 如果left或者right都在起始位置，說(shuō)明不是山峰 
  
  
  
  
        if (left == right && left != 0 && right != A.size() - 1) return true; 
  
  
  
  
        return false; 
  
  
  
  
    } 
  
  
  
  
}; 
 
 
 
 

如果想系統(tǒng)學(xué)一學(xué)雙指針的話(huà)， 可以看一下這篇雙指針?lè)ǎ嚎偨Y(jié)篇!

其他語(yǔ)言版本

Java

 
 
 
 

  
  
  
  
class Solution { 
  
  
  
  
    public boolean validMountainArray(int[] arr) { 
  
  
  
  
        if (arr.length < 3) { // 此時(shí)，一定不是有效的山脈數(shù)組 
  
  
  
  
            return false; 
  
  
  
  
        } 
  
  
  
  
        // 雙指針 
  
  
  
  
        int left = 0; 
  
  
  
  
        int right = arr.length - 1; 
  
  
  
  
        // 注意防止指針越界 
  
  
  
  
        while (left + 1 < arr.length && arr[left] < arr[left + 1]) { 
  
  
  
  
            left++; 
  
  
  
  
        } 
  
  
  
  
        // 注意防止指針越界 
  
  
  
  
        while (right > 0 && arr[right] < arr[right - 1]) { 
  
  
  
  
            right--; 
  
  
  
  
        } 
  
  
  
  
        // 如果left或者right都在起始位置，說(shuō)明不是山峰 
  
  
  
  
        if (left == right && left != 0 && right != arr.length - 1) { 
  
  
  
  
            return true; 
  
  
  
  
        } 
  
  
  
  
        return false; 
  
  
  
  
    } 
  
  
  
  
} 
 
 
 
 

新聞名稱(chēng)：有效的山脈數(shù)組，怎么求？
分享路徑：http://www.dlmjj.cn/article/cdpdidc.html