Say you have an array for which the
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
Example 1:
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.
Example 2:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# O(n^2).
n = len(prices)
res = 0
for i in range(n):
for j in range(i+1, n):
if prices[i] < prices[j] and prices[j] - prices[i] > res:
res = prices[j] - prices[i]
return res
class Solution:
def maxProfit(self, prices: List[int]) -> int:
slow, fast = 0, 0
max_profit = 0
while fast < len(prices):
if prices[fast] > prices[slow]:
max_profit = max(max_profit, prices[fast] - prices[slow])
else:
slow = fast
fast += 1
return max_profit
https://leetcode.com/problems/find-k-closest-elements/ Naive def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]: L = sorted([(abs(elt - x), elt) for elt in arr], key=lambda tup: tup[0]) return sorted([tup[1] for tup in L[:k]]) Opti
Sep 23, 2022Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. push(x) -- Push element x onto stack. pop() -- Removes the element on top of the stack. top() -- Get the top element. getMin() -- Retrieve the minimum element in the stack. Example: MinStack minStack = new MinStack();
Jun 27, 2022Given a string containing just the characters $($, $)$, ${$, $}$, $[$ and $]$, determine if the input string is valid. An input string is valid if: 1. Open brackets must be closed by the same type of brackets. 2. Open brackets must be closed in the correct order. Note that an empty string is also considered valid. Example 1:
Jun 27, 2022Solution 1 Time complexity: O(n³) Space complexity: O(n) class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: n = len(nums) if n < 3: return []
Apr 23, 2022or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up