LeetCode - Algorithms - 20. Valid Parentheses

Difficulty:Easy的题,在面试现场,面对黑板,我毫无头绪没有任何思路,考官已经提示自己你想想有什么数据结构可以利用,自己还是没想通。

This is a problem that’s good to use a stack.

回来上网找线索,主要参考了这个20 LeetCode Java: Valid Parentheses – Easy,此题的关键确实就是数据结构,要用Stack(栈),其实在做表达式解析那两道题227. Basic Calculator II224. Basic Calculator时已经碰到过,自己也做了题,但还是没理解透,遇到新问题又傻眼了。

代码是人家的,天下程序一大抄!!!但不理解的话,代码不会内化于你。看来自己做LeetCode算法题凑数没用,理解不深,做完了又忘了。看来做完了还得温故知新加深理解。

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public boolean isValid(String s) {
HashMap<Character, Character> pair = new HashMap<Character, Character>();
pair.put(')','(');
pair.put('}','{');
pair.put(']','[');
Stack<Character> stk = new Stack<Character>();
char c = '\u0000';
for(int i=0;i<s.length();i++) {
c = s.charAt(i);
switch(c) {
case '{':
case '[':
case '(':
stk.push(c);
break;
default:
if (stk.isEmpty() || pair.get(c)!=stk.pop())
return false;
}
}
if (stk.isEmpty())
return true;
return false;
}
}

Submission Detail

  • 76 / 76 test cases passed.
  • Runtime: 5 ms
  • Your runtime beats 98.09 % of java submissions.

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
var pair = {'\}':'\{','\]':'\[',')':'('};
var stk = new Array();
var c = '';
for(var i=0;i<s.length;i++) {
c = s[i];
switch(c) {
case '{':
case '[':
case '(':
stk.push(c);
break;
default:
if (stk.length==0 || pair[c]!=stk.pop()) {
return false;
}
}
}
if (stk.length==0) return true;
return false;
};

Submission Detail

  • 76 / 76 test cases passed.
  • Runtime: 52 ms
  • Your runtime beats 100.00 % of javascript submissions.

Knowlege points of database especially mysql

Index

The best way to improve the performance of SELECT operations is to create indexes on one or more of the columns that are tested in the query.
Indexes are used to find rows with specific column values quickly. Without an index, MySQL must begin with the first row and then read through the entire table to find the relevant rows. The larger the table, the more this costs. If the table has an index for the columns in question, MySQL can quickly determine the position to seek to in the middle of the data file without having to look at all the data. If a table has 1,000 rows, this is at least 100 times faster than reading sequentially.

Select

表扫描(table scan)

  • 在表扫描中,每一个表中的文件块都会被顺序扫描,而且每一个记录都会被测试,看它是否会满足条件
  • 表扫描是在没有索引的情况下进行的

索引扫描(index scan)

  • 使用索引的扫描算法称之为索引扫描
  • 当有索引的时候,选择运算就会执行索引扫描

MySQL

Truncate diff Delete

TRUNCATE TABLE empties a table completely. It requires the DROP privilege.

Logically, TRUNCATE TABLE is similar to a DELETE statement that deletes all rows, or a sequence of DROP TABLE and CREATE TABLE statements. To achieve high performance, it bypasses the DML method of deleting data. Thus, it cannot be rolled back, it does not cause ON DELETE triggers to fire, and it cannot be performed for InnoDB tables with parent-child foreign key relationships.

Although TRUNCATE TABLE is similar to DELETE, it is classified as a DDL statement rather than a DML statement.

  • Any AUTO_INCREMENT value is reset to its start value. This is true even for MyISAM and InnoDB, which normally do not reuse sequence values.
  • When used with partitioned tables, TRUNCATE TABLE preserves the partitioning; that is, the data and index files are dropped and re-created, while the partition definitions (.par) file is unaffected.
  • The TRUNCATE TABLE statement does not invoke ON DELETE triggers.

ref

Partitioning

MySQL 5.6 Community binaries provided by Oracle include partitioning support.

SELECT PLUGIN_NAME as Name, PLUGIN_VERSION as Version, PLUGIN_STATUS as Status FROM INFORMATION_SCHEMA.PLUGINS WHERE PLUGIN_TYPE='STORAGE ENGINE';
Name Version Status
partition 1.0 ACTIVE

Sharding

  • 分片、分库分表(Sharding)
  • 以 MySQL 为例,分库分表从阶段应该拆分为分表、分库,一般来说是先进行分表,分表的原动力在于 MySQL 单表性能问题
  • 是由于业务的不可控,所以大家往往采取比较保守的策略,这就是分表的原因。
  • 分库主要由于 MySQL 容量上,MySQL 的写入是很昂贵的操作。目前有一些云 RDS 通过计算与存储分离、log is database 的理念来很大程度解决了写入扩大的问题,但在这之前,更为普遍的解决方案就是把一个集群拆分成 N 个集群,即分库分表(sharding)。为了规避热点问题,绝大多数采用的方法就是 hash 切分,也有极少的范围、或者基于 Mapping 的查询切分。
  • 既然做了分表,那数据的分发、路由就需要进行处理,自下而上分为三层,分别 DB 层、中间层、应用层。DB 层实现,简单来说就是把路由信息加入到某个 Metedata 节点,同时加上一些诸如读写分离、HA 整合成一个 DB 服务或者产品,但这种方案实现复杂度非常高,有的逐步演变成了一种新的数据库,更为常见的是在中间层实现,而中间层又根据偏向 DB 还是偏向应用分为 DB proxy 和 JDBC proxy。
  • DB proxy高度依赖网络组件,它需要诸如 LVS/F5 等 VIP 来实现流量的负载均衡,如果跨 IDC,还依赖诸如 DNS 进行IDC 分发。同时部分 DBproxy 对 Prepare 这类操作支持不友好,所以它的问题概括来说:
    • 链路过长,每层都会增加响应时间
    • 网络单点,并且往往是整个公司层面的单点
    • 部分产品对Prepare 应用不友好,需要绑定 connection 信息
  • JDBC proxy最大的问题是违背了 DB 透明的原则,它需要对不同的语言编写 Driver,概括来说:
    • 语言限制,总会遭到一批 RD 同学的吐槽 “世界上最好的语言竟然不支持!”
    • 接入繁琐
    • DB 不透明

ref

LeetCode - Algorithms - 106. Construct Binary Tree from Inorder and Postorder Traversal

这题跟105. Construct Binary Tree from Preorder and Inorder Traversal是一个系列,代码抄袭了Construct Binary Tree from Inorder and Postorder Traversal,二叉树的算法应该说不难理解。

From the post-order array, we know that last element is the root. We can find the root in in-order array. Then we can identify the left and right sub-trees of the root from in-order array. Using the length of left sub-tree, we can identify left and right sub-trees in post-order array. Recursively, we can build up the tree.

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
int inStart=0;
int inEnd=inorder.length-1;
int postStart=0;
int postEnd=postorder.length-1;
return buildTree(inorder,inStart,inEnd,postorder,postStart,postEnd);
}

public TreeNode buildTree(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
if (inStart>inEnd || postStart>postEnd)
return null;

int rtVal = postorder[postEnd];
TreeNode rt = new TreeNode(rtVal);

int k=0;
for(int i=0;i<=inEnd;i++) {
if (inorder[i]==rtVal) {
k=i;
break;
}
}

rt.left = buildTree(inorder,inStart,k-1,postorder, postStart, postStart+k-inStart-1);
rt.right = buildTree(inorder,k+1,inEnd,postorder,postStart+k-inStart,postEnd-1);

return rt;
}
}

Submission Detail

  • 203 / 203 test cases passed.
  • Runtime: 18 ms
  • Your runtime beats 25.95 % of java submissions.

LeetCode - Algorithms - 105. Construct Binary Tree from Preorder and Inorder Traversal

二叉树自己能理解一二,不算难。自己也观察出来了从Preorder里知道根结点,再在Inorder里划分左右子树,如此不断递归二分。代码抄袭了这个的:
LeetCode – Construct Binary Tree from Preorder and Inorder Traversal (Java)

From the pre-order array, we know that first element is the root. We can find the root in in-order array. Then we can identify the left and right sub-trees of the root from in-order array. Using the length of left sub-tree, we can identify left and right sub-trees in pre-order array. Recursively, we can build up the tree.

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
int preStart=0;
int preEnd=preorder.length-1;
int inStart = 0;
int inEnd = inorder.length-1;
return buildTree(preorder,preStart,preEnd,inorder,inStart,inEnd);
}

public TreeNode buildTree(int[] preorder, int preStart,int preEnd, int[] inorder, int inStart, int inEnd) {
if (preStart>preEnd || inStart>inEnd)
return null;

int val = preorder[preStart];
TreeNode rt = new TreeNode(val);

int k=0;
for(int i=0;i<=inEnd;i++) {
if (inorder[i]==val) {
k=i;
break;
}
}

rt.left = buildTree(preorder, preStart+1, preStart+(k-inStart),inorder,inStart,k-1);
rt.right = buildTree(preorder, preStart+(k-inStart)+1, preEnd, inorder, k+1, inEnd);

return rt;
}
}

Submission Detail

  • 203 / 203 test cases passed.
  • Runtime: 13 ms
  • Your runtime beats 55.29 % of java submissions.

LeetCode - Algorithms - 518. Coin Change 2

变个样,又不知道怎么解决了,动态规划确实不是那么好理解。根据上一题的经验,还是从递归入手,先实现递归,再琢磨动态规划的解决方案,就有点循序渐进的味道。正如 What is an easy way to understand the coin change problem in dynamic programming? 的一个回答所言:

Instead of thinking about filling a matrix, think in terms of the recurrence relation. I have seen a lot of people who try to think dynamic programming problems in terms of filling a table/array. But this approach is problematic. For example, if the state representation has more than two dimensions, then this approach does not help much.

The essence of dynamic programming is the idea of a state space and a recurrence relation between states. Once you figure that out for any problem, implementation is straightforward.

参考了这些,虽然还是没有完全理解,程序在leetcode上通过了,程序其实就短短的几行,The code has a O(NC) pseudo-polynomial complexity where N is the amount and C the number of input coins

Java

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public int change(int amount, int[] coins) {
int[] dp = new int[amount+1];
dp[0]=1;
for(int i=0;i<coins.length;i++) {
for(int j=coins[i];j<=amount;++j) {
dp[j]+=dp[j-coins[i]];
}
}
return dp[amount];
}
}

Submission Detail

  • 27 / 27 test cases passed.
  • Runtime: 4 ms
  • Your runtime beats 78.72 % of java submissions.

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* @param {number} amount
* @param {number[]} coins
* @return {number}
*/
var change = function(amount, coins) {
var dp = new Array(amount+1);
for(var i=0;i<dp.length;i++)
dp[i]=0;
dp[0]=1;
for(var i=0;i<amount;i++)
for(var j=coins[i];j<=amount;++j)
dp[j]+=dp[j-coins[i]];
return dp[amount];
};

Submission Detail

  • 27 / 27 test cases passed.
  • Runtime: 60 ms
  • Your runtime beats 89.86 % of javascript submissions.

LeetCode - Algorithms - 322. Coin Change

被这题卡住了,因为动态规划好像不好理解,看《算法图解》第九章,说动态规划都从一个网格开始,需要具备 Overlapping Sub-problemsOptimal Substructure。上网找线索与提示,最后发现先用递归方式实现,再看动态规划的方案就好理解些。主要参考了这几个:

原来 Change-making problemKnapsack problem 的一类,背包问题还属于NP问题呢。

此题递归方式的实现是指数时间复杂度,跟动态规划的实现相比差距确实极其明显。递归方式的解法完全不可用,输入[1,2,5],100则报Time Limit Exceeded。

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public int coinChange(int[] coins, int amount) {
if (amount==0) return 0;

int n=-1;

int[] MC = new int[amount+1];
MC[0]=0;
for(int i=1;i<=amount;i++) {
MC[i] = Integer.MAX_VALUE;
}

for(int i=1;i<=amount;i++) {
for(int j=0;j<coins.length;j++) {
if (i>=coins[j]) {
int numCoins = MC[i-coins[j]];
if (numCoins!=Integer.MAX_VALUE && (numCoins+1<MC[i])) {
MC[i] = numCoins+1;
}
}
}
}
n=MC[amount];

if (n==Integer.MIN_VALUE || n==Integer.MAX_VALUE || n==0) n = -1;
return n;
}
}

Submission Detail

  • 182 / 182 test cases passed.
  • Runtime: 37 ms
  • Your runtime beats 28.19 % of java submissions.

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
* @param {number[]} coins
* @param {number} amount
* @return {number}
*/
var coinChange = function(coins, amount) {
if (amount==0) return 0;

var n=-1;
var MC = new Array(amount+1);
MC[0]=0;
for(var i=1;i<=amount;i++)
MC[i]=Number.MAX_VALUE;

for(var i=1;i<=amount;i++) {
for(var j=0;j<coins.length;j++) {
if (i>=coins[j]) {
var cc = MC[i-coins[j]];
if (cc!=Number.MAX_VALUE && (cc+1<MC[i]))
MC[i] = cc+1;
}
}
}
n = MC[amount];

if (n==Number.MIN_VALUE || n==Number.MAX_VALUE || n==0) n = -1;

return n;
};

Submission Detail

  • 182 / 182 test cases passed.
  • Runtime: 80 ms
  • Your runtime beats 95.69 % of javascript submissions.

LeetCode - Algorithms - 224. Basic Calculator

Java

1

代码见前一篇

Submission Detail

  • 37 / 37 test cases passed.
  • Runtime: 143 ms
  • Your runtime beats 6.05 % of java submissions.

2 Shunting-yard algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
import java.util.StringTokenizer;

class Solution {
public int calculate(String s) {
return evalRPN(infixToPostfix(s.replaceAll(" ","")));
}

private int evalRPN(List<String> exprlist){
LinkedList<Integer> stack = new LinkedList<Integer>();

for (String token : exprlist) {
Integer tokenNum = null;
try{
tokenNum = Integer.parseInt(token);
}catch(NumberFormatException e){}
if(tokenNum != null){
stack.push(Integer.parseInt(token+""));
}else if(token.equals("-")){
int secondOperand = stack.pop();
int firstOperand = stack.pop();
stack.push(firstOperand - secondOperand);
}else if(token.equals("+")){
int secondOperand = stack.pop();
int firstOperand = stack.pop();
stack.push(firstOperand + secondOperand);
}else{
return 0;
}
}
int r = stack.pop();
return r;
}

private List<String> infixToPostfix(String infix) {
List<String> list = new ArrayList<String>();
final String ops = "-+";

Stack<Integer> stack = new Stack<Integer>();

StringTokenizer st = new StringTokenizer(infix,"[\\+\\-()]",true);
while (st.hasMoreTokens()) {
String token = st.nextToken();
if (token.isEmpty())
continue;
char c = token.charAt(0);
int idx = ops.indexOf(c);

if (idx != -1) {
if (stack.isEmpty())
stack.push(idx);

else {
while (!stack.isEmpty()) {
int prec2 = stack.peek() / 2;
int prec1 = idx / 2;
if (prec2 > prec1 || prec2 == prec1)
list.add( ops.charAt(stack.pop()) + "" );
else break;
}
stack.push(idx);
}
}
else if (c == '(') {
stack.push(-2);
}
else if (c == ')') {
while (stack.peek() != -2)
list.add( ops.charAt(stack.pop())+"" );
stack.pop();
}
else {
list.add( token );
}
}
while (!stack.isEmpty())
list.add( ops.charAt(stack.pop())+"" );
return list;
}
}

Submission Detail

  • 37 / 37 test cases passed.
  • Runtime: 172 ms, faster than 7.80% of Java online submissions for Basic Calculator.
  • Memory Usage: 55.4 MB, less than 20.00% of Java online submissions for Basic Calculator.

Resources

LeetCode - Algorithms - 227. Basic Calculator II

这题是关于表达式解析的,2007年学习数据结构曾经实现过,思路是把中缀表达式转换为后缀表达式,再结合栈这种数据结构计算后缀表达式,就拿来执行下,结果LeetCode test case 1*2-3/4+5*6-7*8+9/10 报了个错 java.lang.ArithmeticException: / by zero,用StringTokenizer把操作符与操作数拆开,改了下原来的代码,最终运行通过了,但自己对其中的机理还是有点知其然而不知其所以然。

原来java7以后可以在switch的case语句里用String类型。

Strings in switch Statements

In the JDK 7 release, you can use a String object in the expression of a switch statement.

Basic Calculator这系列的题看来也是比较经典的,表达式解析好像是数据结构与编译原理的交叉点之一。

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;

class Solution {
public int postfixCalculator(List<String> postfixExpr) {
Stack<Integer> stk = new Stack<Integer>();
for (int i = 0; i < postfixExpr.size(); i++) {
String s = postfixExpr.get(i);
int a, b, x;
switch (s) {
case "*":
if (!stk.isEmpty()) {
a = stk.pop().intValue();
b = stk.pop().intValue();
x = a * b;
stk.push(new Integer(x));
}
break;
case "+":
if (!stk.isEmpty()) {
a = stk.pop().intValue();
b = stk.pop().intValue();
x = a + b;
stk.push(new Integer(x));
}
break;
case "-":
if (!stk.isEmpty()) {
a = stk.pop().intValue();
b = stk.pop().intValue();
x = b - a;
stk.push(new Integer(x));
}
break;
case "/":
if (!stk.isEmpty()) {
a = stk.pop().intValue();
b = stk.pop().intValue();
x = b / a;
stk.push(new Integer(x));
}
break;
default:
stk.push(new Integer(s));
break;
}
}
int ret = 0;
if (!stk.isEmpty())
ret = stk.pop().intValue();
return ret;
}

public List<String> infix2postfix(String infixExpr) {
List<String> r = new ArrayList<String>();
Stack<String> stk = new Stack<String>();
List<String> list = new ArrayList<String>();
StringTokenizer st = new StringTokenizer(infixExpr,"[\\+\\-\\*/()]",true);
while (st.hasMoreTokens()) {
list.add(st.nextToken());
}
for (int i = 0; i < list.size(); i++) {
String s = list.get(i);
switch (s) {
case "*":
case "/":
while (!stk.isEmpty() && (stk.peek().equals("*") || stk.peek().equals("/"))) {
r.add( stk.pop() );
}
stk.push(s);
break;
case "+":
case "-":
while (!stk.isEmpty() && !stk.peek().equals("(")) {
r.add( stk.pop() );
}
stk.push(s);
break;
case "(":
stk.push(s);
break;
case ")":
while (!stk.isEmpty() && !stk.peek().equals("(")) {
r.add(stk.pop());
}
if (stk.peek().equals("("))
stk.pop();
break;
default:
r.add(s);
}
}

while (stk != null && !stk.isEmpty()) {
r.add( stk.pop() );
}

return r;
}

public int calculate(String s) {
return postfixCalculator(infix2postfix(s.replaceAll(" ", "")));
}
}

Submission Detail

  • 109 / 109 test cases passed.
  • Runtime: 98 ms
  • Your runtime beats 5.79 % of java submissions.

LeetCode - Algorithms - 122. Best Time to Buy and Sell Stock II

自己已经意识到就是在输入数组里找递增子序列,但还是没想通。上网找点提示,参考了LeetCode – Best Time to Buy and Sell Stock II (Java),看了人家的,恍然大悟,不难,但就是想不到。

这系列 Best Time to Buy and Sell Stock 的题看来也是比较经典的

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int maxProfit(int[] prices) {
int profit = 0;
int diff = 0;
for(int i=1;i<prices.length;i++) {
diff = prices[i]-prices[i-1];
if (diff>0) {
profit+=diff;
}
}
return profit;
}
}

Submission Detail

  • 201 / 201 test cases passed.
  • Your runtime beats 99.86 % of java submissions.

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
var profit = 0;
var diff = 0;
for(var i=1;i<prices.length;i++) {
diff = prices[i]-prices[i-1];
if (diff>0)
profit+=diff;
}
return profit;
};

Submission Detail

  • 201 / 201 test cases passed.
  • Your runtime beats 18.88 % of javascript submissions.

LeetCode - Algorithms - 121. Best Time to Buy and Sell Stock

虽然难度标为Easy,但自己居然提交了好几次才通过了,而且是因为犯了逻辑错误。最后用个二重循环,倒也简单,但性能不好,不知道高效算法是如何做的?

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int maxProfit(int[] prices) {
if (prices==null || prices.length==0)
return 0;
int r = 0;
for(int i=0;i<prices.length-1;i++) {
for(int j=prices.length-1;j>i;j--) {
if (prices[j]-prices[i]>r) {
r = prices[j]-prices[i];
}
}
}
return r;
}
}

Submission Detail

  • 200 / 200 test cases passed.
  • Your runtime beats 4.30 % of java submissions.

在网上人家的一个O(n)时间复杂度的算法

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int maxProfit(int[] prices) {
if (prices==null || prices.length<=1)
return 0;
int r = 0;
int minPrice = prices[0];
for(int i=1;i<prices.length;i++) {
r = Math.max(r, prices[i]-minPrice);
minPrice = Math.min(minPrice, prices[i]);
}
return r;
}
}

Submission Detail

  • 200 / 200 test cases passed.
  • Your runtime beats 32.88 % of java submissions.

JavaScript

O(n2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
if (prices==null || prices.length==0)
return 0;
var r=0;
var x = 0;
for(var i=0;i<prices.length-1;i++) {
for(var j=prices.length-1;j>i;j--) {
x = prices[j]-prices[i];
if (x>r)
r = x;
}
}
return r;
};

Submission Detail

  • 200 / 200 test cases passed.
  • Your runtime beats 7.71 % of javascript submissions.

O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
if (prices==null || prices.length<=1)
return 0;
var r=0;
var minPrice = prices[0];
for(var i=1;i<prices.length;i++) {
r = Math.max(r,prices[i]-minPrice);
minPrice = Math.min(minPrice,prices[i]);
}
return r;
};

Submission Detail

  • 200 / 200 test cases passed.
  • Your runtime beats 84.89 % of javascript submissions.