<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ??一站式輕松地調用各大LLM模型接口,支持GPT4、智譜、豆包、星火、月之暗面及文生圖、文生視頻 廣告
                # 0121. 買賣股票的最佳時機 ## 題目地址(121. 買賣股票的最佳時機) <https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/description/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個數組,它的第 i 個元素是一支給定股票第 i 天的價格。 如果你最多只允許完成一筆交易(即買入和賣出一支股票一次),設計一個算法來計算你所能獲取的最大利潤。 注意:你不能在買入股票前賣出股票。 示例 1: 輸入: [7,1,5,3,6,4] 輸出: 5 解釋: 在第 2 天(股票價格 = 1)的時候買入,在第 5 天(股票價格 = 6)的時候賣出,最大利潤 = 6-1 = 5 。 注意利潤不能是 7-1 = 6, 因為賣出價格需要大于買入價格;同時,你不能在買入前賣出股票。 示例 2: 輸入: [7,6,4,3,1] 輸出: 0 解釋: 在這種情況下, 沒有交易完成, 所以最大利潤為 0。 ``` ``` ## 前置知識 - [數組](https://github.com/azl397985856/leetcode/blob/master/thinkings/basic-data-structure.md) ## 公司 - 阿里 - 騰訊 - 百度 - 字節 - amazon - bloomberg - facebook - microsoft - uber ## 思路 由于我們是想獲取到最大的利潤,我們的策略應該是低點買入,高點賣出。 由于題目對于交易次數有限制,只能交易一次,因此問題的本質其實就是求波峰浪谷的差值的最大值。 用圖表示的話就是這樣: ![](https://img.kancloud.cn/a4/98/a49859816a3e8d63b42de5a218b93cf7_700x434.jpg) ## 關鍵點解析 - 這類題只要你在心中(或者別的地方)畫出上面這種圖就很容易解決 ## 代碼 語言支持:JS,C++,Java,Python JS Code: ``` <pre class="calibre18">``` <span class="hljs-title">/** * @param {number[]} prices * @return {number} */</span> <span class="hljs-keyword">var</span> maxProfit = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">prices</span>) </span>{ <span class="hljs-keyword">let</span> min = prices[<span class="hljs-params">0</span>]; <span class="hljs-keyword">let</span> profit = <span class="hljs-params">0</span>; <span class="hljs-title">// 7 1 5 3 6 4</span> <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">1</span>; i < prices.length; i++) { <span class="hljs-keyword">if</span> (prices[i] > prices[i - <span class="hljs-params">1</span>]) { profit = <span class="hljs-params">Math</span>.max(profit, prices[i] - min); } <span class="hljs-keyword">else</span> { min = <span class="hljs-params">Math</span>.min(min, prices[i]); } } <span class="hljs-keyword">return</span> profit; }; ``` ``` C++ Code: ``` <pre class="calibre18">``` <span class="hljs-title">/** * 系統上C++的測試用例中的輸入有[],因此需要加一個判斷 */</span> <span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">maxProfit</span><span class="hljs-params">(<span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>>& prices)</span> </span>{ <span class="hljs-keyword">if</span> (prices.empty()) <span class="hljs-keyword">return</span> <span class="hljs-params">0</span>; <span class="hljs-keyword">auto</span> min = prices[<span class="hljs-params">0</span>]; <span class="hljs-keyword">auto</span> profit = <span class="hljs-params">0</span>; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">auto</span> i = <span class="hljs-params">1</span>; i < prices.size(); ++i) { <span class="hljs-keyword">if</span> (prices[i] > prices[i <span class="hljs-params">-1</span>]) { profit = max(profit, prices[i] - min); } <span class="hljs-keyword">else</span> { min = <span class="hljs-params">std</span>::min(min, prices[i]);; } } <span class="hljs-keyword">return</span> profit; } }; ``` ``` Java Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> </span>{ <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">maxProfit</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] prices)</span> </span>{ <span class="hljs-keyword">int</span> minprice = Integer.MAX_VALUE; <span class="hljs-keyword">int</span> maxprofit = <span class="hljs-params">0</span>; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> price: prices) { maxprofit = Math.max(maxprofit, price - minprice); minprice = Math.min(price, minprice); } <span class="hljs-keyword">return</span> maxprofit; } } ``` ``` Python Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxProfit</span><span class="hljs-params">(self, prices: <span class="hljs-string">'List[int]'</span>)</span> -> int:</span> <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> prices: <span class="hljs-keyword">return</span> <span class="hljs-params">0</span> min_price = float(<span class="hljs-string">'inf'</span>) max_profit = <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> price <span class="hljs-keyword">in</span> prices: <span class="hljs-keyword">if</span> price < min_price: min_price = price <span class="hljs-keyword">elif</span> max_profit < price - min_price: max_profit = price - min_price <span class="hljs-keyword">return</span> max_profit ``` ``` **復雜度分析** - 時間復雜度:O(N)O(N)O(N) - 空間復雜度:O(1)O(1)O(1) ## 相關題目 - [122.best-time-to-buy-and-sell-stock-ii](122.best-time-to-buy-and-sell-stock-ii.html) - [309.best-time-to-buy-and-sell-stock-with-cooldown](309.best-time-to-buy-and-sell-stock-with-cooldown.html) 大家對此有何看法,歡迎給我留言,我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫:<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看