C++?LeetCode1827題解最少操作使數(shù)組遞增
LeetCode1827.最少操作使數(shù)組遞增
力扣題目鏈接：leetcode.cn/problems/mi…
給你一個整數(shù)數(shù)組 nums （下標(biāo)從 0 開始）。每一次操作中，你可以選擇數(shù)組中一個元素，并將它增加 1 。
- 比方說，如果
nums = [1,2,3]，你可以選擇增加nums[1]得到nums = [1,3,3]。
請你返回使 nums 嚴(yán)格遞增 的 最少 操作次數(shù)。
我們稱數(shù)組 nums 是 嚴(yán)格遞增的 ，當(dāng)它滿足對于所有的 0 <= i < nums.length - 1 都有 nums[i] < nums[i+1] 。一個長度為 1 的數(shù)組是嚴(yán)格遞增的一種特殊情況。
示例 1：
輸入：nums = [1,1,1]
輸出：3
解釋：你可以進行如下操作：
1) 增加 nums[2] ，數(shù)組變?yōu)?[1,1,2] 。
2) 增加 nums[1] ，數(shù)組變?yōu)?[1,2,2] 。
3) 增加 nums[2] ，數(shù)組變?yōu)?[1,2,3] 。
示例 2：
輸入：nums = [1,5,2,4,1]
輸出：14
示例 3：
輸入：nums = [8]
輸出：0
提示：
1 <= nums.length <= 50001 <= nums[i] <= 104
方法一：遍歷
數(shù)字只增不減，還想要整個數(shù)組遞增，那么肯定是從前往后處理一遍數(shù)組，如果這個數(shù)比前一個數(shù)小，那么就讓這個數(shù)變大。
那么變成多大呢？
為了減少“增加操作”的次數(shù)，當(dāng)然是變得越小越好。
因此，我們從前往后遍歷數(shù)組，如果數(shù)組中某個元素的值不大于前一個元素，那么就將這個數(shù)通過“數(shù)次加一操作”變成上一個元素+1
- 時間復(fù)雜度O(len(nums))
- 空間復(fù)雜度O(1)
AC代碼
C++
class Solution {
public:
int minOperations(vector<int>& nums) {
int ans = 0;
for (int i = 1; i < nums.size(); i++) {
if (nums[i] <= nums[i - 1]) {
ans += nums[i - 1] + 1 - nums[i];
nums[i] = nums[i - 1] + 1;
}
}
return ans;
}
};以上就是C++ LeetCode1827題解最少操作使數(shù)組遞增的詳細內(nèi)容，更多關(guān)于C++ 最少操作數(shù)組遞增的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
右值引用（及其支持的Move語意和完美轉(zhuǎn)發(fā)）是C++0x將要加入的最重大語言特性之一。這篇文章主要介紹了C++11右值引用和std::move語句實例解析,非常不錯，具有參考借鑒價值，需要的朋友可以參考下2017-03-03
c 調(diào)用python出現(xiàn)異常的原因分析
本篇文章是對使用c語言調(diào)用python出現(xiàn)異常的原因進行了詳細的分析介紹，需要的朋友參考下2013-05-05
這篇文章主要介紹了c++版線程池和任務(wù)池，實現(xiàn)任務(wù)執(zhí)行完畢線程退出.在linux下壓力測試通過2014-03-03
給數(shù)組分配多大的空間？你是否和初學(xué)C時的我一樣，有過這樣的疑問。這一期就來聊一聊動態(tài)內(nèi)存的分配，讀完這篇文章，你可能對內(nèi)存的分配有一個更好的理解2022-04-04
這篇文章主要為大家詳細介紹了C語言實現(xiàn)掃雷小程序，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-08-08
C++11的新特性可變參數(shù)模板能夠讓我們創(chuàng)建可以接受可變參數(shù)的函數(shù)模板和類模板，相比C++98和C++03，類模板和函數(shù)模板中只能含固定數(shù)量的模板參數(shù)，可變參數(shù)模板無疑是一個巨大的改進，這篇文章主要介紹了C++11中的可變參數(shù)模板/lambda表達式,需要的朋友可以參考下2023-03-03
Qt使用QChart實現(xiàn)動態(tài)顯示溫度變化曲線
Qt的QChart是一個用于繪制圖表和可視化數(shù)據(jù)的類，提供了一個靈活的、可擴展的、跨平臺的圖表繪制解決方案，所以本文就將使用QChart實現(xiàn)動態(tài)顯示3個設(shè)備的溫度變化曲線，感興趣的可以了解一下2023-06-06
這篇文章主要介紹了VC動態(tài)生成菜單項的實現(xiàn)方法,在桌面應(yīng)用程序開發(fā)中常會用到的一個功能,需要的朋友可以參考下2014-08-08
linux內(nèi)核select/poll，epoll實現(xiàn)與區(qū)別
這篇文章主要介紹了linux內(nèi)核select/poll，epoll實現(xiàn)與區(qū)別,需要的朋友可以參考下2016-11-11
這篇文章主要介紹了C++ 中二分查找遞歸非遞歸實現(xiàn)并分析的相關(guān)資料,需要的朋友可以參考下2017-06-06