【数组】941. 有效的山脉数组 #6

Activity

1. lyonyang

   added

   数组

   on Jul 26, 2021
2. zhangke666163 commented on Jul 29, 2021

   

   zhangke666163

   on Jul 29, 2021

   More actions

   思路：

   1. 遍历数组，找出最大的元素item
   2. 遍历数组，左边元素递增且小于最大元素，右边元素递减小于最大元素
   3. 用一个容器存储每一个元素是否满足条件的结果
      时间、空间复杂度：O(n)
      代码：

   def is_mountain_array(array):
       max_item = array[0]
       if len(array) < 3:
           return False
       # 1. 找出最大元素
       for i in range(len(array)):
           if array[i] > max_item:
               max_item = array[i]
       if max_item in [array[0], array[-1]]:
           return False
       item_index = array.index(max_item)
       # 每个元素是否满足规则
       is_ok = []
       for i in range(len(array)-1):
           if i < item_index:
               # 左边元素
               if array[i] < array[i+1]:
                   is_ok.append(True)
               else:
                   is_ok.append(False)
               continue
           # 右边元素
           if i >= item_index:
               if array[i] > array[i+1]:
                   is_ok.append(True)
               else:
                   is_ok.append(False)
               continue
       if False in is_ok:
           return False
       else:
           return True
   if __name__ == '__main__':
       print(is_mountain_array([1, 2, 3, 3, 1]))
   
3. xuezc1119 commented on Jul 29, 2021

   

   xuezc1119

   on Jul 29, 2021

   More actions

   思路

   递增判断并获取到目前为止的最大值
   最大值后半段递减判断
   第一个和最后一个都不能是最大值

   复杂度

   时间复杂度O(n)，空间复杂度O(1)

   代码

   /**
   * @param {number[]} arr
   * @return {boolean}
   */
   var validMountainArray = function(arr) {
       if(arr && arr.length < 3) return false;
       let increase = arr[0];
       for (let i = 1; i < arr.length; i++) {
           if (increase < arr[i]) { // 递增
               increase = arr[i];
               if (i == arr.length-1) return false; // 只增不减
           } else { // 假定这个是最大值
               if (i == 1) return false; // 第一个大于第二个
               let data = arr.slice(i-1); // 截取后半段
               let decrease = data[0];
               for (let j = 1; j < data.length; j++) { // 后半段递减判断
                   if (decrease <= data[j]) return false;
                   decrease = data[j];
               }
               break;
           }
       }
       return true;
   };
4. lyonyang

   added

   第1周

   简单

   on Aug 7, 2021
5. lyonyang commented on Aug 7, 2021

   

   lyonyang

   on Aug 7, 2021

   MemberAuthor

   More actions

   思路一 - 标志判断

   定义一个标志位 , 标志是处于上升阶段还是下降阶段

   注意 : 标志位最终结果必须标志着下降才是有效的山脉数组

   # flag = 0 标志着处于上升阶段
   # flag = 1 标志着处于下降阶段
   class Solution:
       def validMountainArray(self, arr: List[int]) -> bool:
           flag = 0
           for i in range(len(arr) - 1):
               if arr[i] == arr[i + 1]:
                   return False
               # 上升
               if flag == 0:
                   if arr[i] > arr[i + 1]:
                       if i == 0:
                           return False
                       flag = 1
               # 下降
               else:
                   if arr[i] < arr[i + 1]:
                       return False
           if flag == 0:
               return False
           return True

   时间复杂度：$O(N)$ , N 为数组长度

   空间复杂度：$O(1)$

   思路二 - 双指针

   利用双指针 , 分别同时从左右两边进行遍历 , 当左右指针都开始下降时停止 , 如果此时左右指针相等则为有效山脉 , 否则无效

   注意 : 结束循环时 , 左指针不能是第一个元素 , 右指针不能是最后一个元素

   class Solution:
       def validMountainArray(self, A) -> bool:
           if len(A) < 3: return False
           left, right = 0, len(A) - 1
           while left < right:
               # 左指针右移
               if A[left] < A[left + 1]:
                   left += 1
                   continue
               elif A[left] == A[left + 1]:
                   return False
               # 右指针左移
               if A[right] < A[right - 1]:
                   right -= 1
                   continue
               elif A[right] == A[right - 1]:
                   return False
               # 如果左有指针都不移动了就结束循环
               break
           if left == right and right != len(A) - 1 and left != 0:
               return True
           return False

   时间复杂度：$O(N)$ , N 为数组长度

   空间复杂度：$O(1)$