Given a 0-indexed integer array nums
, return true
if it can be made strictly increasing after removing exactly one element, or false
otherwise. If the array is already strictly increasing, return true
.
The array nums
is strictly increasing if nums[i - 1] < nums[i]
for each index (1 <= i < nums.length).
Example 1:
Input: nums = [1,2,10,5,7] Output: true Explanation: By removing 10 at index 2 from nums, it becomes [1,2,5,7]. [1,2,5,7] is strictly increasing, so return true.
Example 2:
Input: nums = [2,3,1,2] Output: false Explanation: [3,1,2] is the result of removing the element at index 0. [2,1,2] is the result of removing the element at index 1. [2,3,2] is the result of removing the element at index 2. [2,3,1] is the result of removing the element at index 3. No resulting array is strictly increasing, so return false.
Example 3:
Input: nums = [1,1,1] Output: false Explanation: The result of removing any element is [1,1]. [1,1] is not strictly increasing, so return false.
Constraints:
2 <= nums.length <= 1000
1 <= nums[i] <= 1000
Solution 1: Brute Force
Enumerate the element to remove and check.
Time complexity: O(n2)
Space complexity: O(n) -> O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua class Solution { public: bool canBeIncreasing(vector<int>& nums) { const int n = nums.size(); auto check = [&](int k) { vector<int> arr(nums); arr.erase(begin(arr) + k); for (int i = 1; i < n - 1; ++i) if (arr[i] <= arr[i - 1]) return false; return true; }; for (int i = 0; i < n; ++i) if (check(i)) return true; return false; } }; |
C++/O(1) Space
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua class Solution { public: bool canBeIncreasing(vector<int>& nums) { const int n = nums.size(); auto check = [&](int k) { for (int i = 1; i < n; ++i) { int j = (i - 1 == k) ? (i - 2) : (i - 1); if (i != k && j >= 0 && nums[i] <= nums[j]) return false; } return true; }; for (int i = 0; i < n; ++i) if (check(i)) return true; return false; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment